Codeforces Round #521 (Div. 3)
A. Frog Jumping
题意：一只青蛙在坐标O点，给出两个数字a和b，并给出一个数字k表示跳跃的次数，第一次跳从O点往右跳a的距离，第二次跳从上一次的位置往左跳b的距离，再第三次从上一次的位置往右跳a的距离…问跳完k次的坐标。
思路：直接算。
AC代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
int T;
ll a, b, k;
scanf("%d", &T);
while(T--) {
scanf("%lld%lld%lld", &a, &b, &k);
ll ans = 0;
ans += k / 2 * (a - b);
if(k & 1)
ans += a;
printf("%lld\n", ans);
}
return 0;
}
B. Disturbed People
题意: 给出一个长度为n(3 ≤ n ≤ 100)的数组，可能为1或者0，1表示这层亮灯，0表示没亮灯。没有亮灯的用户会被亮灯的用户打扰的条件是：他没亮灯，但他的左右都亮着灯。现在要求让所有人都不被打扰，求最少需要灭掉的灯的数量。
思路: 如果是“1 0 1 0 1”这样的串，那么我们只需要关掉最中间的一个灯即可，故我的思路是记录下所有0的位置，再模拟找是否存在这种连续的10101串。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 105;
int a[maxn], mark[maxn];
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
int tot = 0;
for(int i = 1; i < n-1; ++i) {
if(a[i] == 0) {
if(a[i-1] == 1 && a[i+1] == 1) {
mark[tot++] = I;
}
}
}
int ans = 0;
for(int i = 0; i < tot; ++i) {
int ss = 1;
while(i+1 < tot && mark[i+1] - mark[i] == 2) {
++ss;
++i;
}
ans += ceil((double)ss/2.0);
}
printf("%d\n", ans);
return 0;
}
C. Good Array
题意：给出一个长度为n()的数组，我们称一个数组“good”当且仅当删掉这个数组中的一个数字之后，存在一个数等于其他数字的和，现在问多少个数字单独被删掉后可以构成“good”数组，并输出这些被删掉的数字的下标（按任意顺序输出即可）。
思路：若一个数字是其他数字的和，那么就是说sum/2这个数字一定存在。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll a[maxn];
map<ll, int> mp;
vector<int> vec;
int main() {
int n;
ll sum = 0;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
++mp[a[i]];
sum += a[i];
}
ll sum2;
for(int i = 0; i < n; ++i) {
sum2 = (sum - a[i])/2;
if(sum2 * 2 != (sum - a[i]))
continue;
if(sum2 == a[i]) {
if(mp[sum2] > 1)
vec.push_back(i+1);
}
else {
if(mp[sum2])
vec.push_back(i+1);
}
}
int len = (int)vec.size();
printf("%d\n", len);
for(int i = 0; i < len; ++i) {
if(i != 0) printf(" ");
printf("%d", vec[i]);
}
printf("\n");
return 0;
}
D. Cutting Out
题意：给出一个长度为n的数组，现在要找一个长度为k的数组，使得原数组减长度为k的数组的次数尽量的多，并输出这个长度为k的数组。
