Codeforces Round #521 (Div. 3)
A. Frog Jumping
題意：一只青蛙在坐標(biāo)O點(diǎn)，給出兩個(gè)數(shù)字a和b，并給出一個(gè)數(shù)字k表示跳躍的次數(shù)，第一次跳從O點(diǎn)往右跳a的距離，第二次跳從上一次的位置往左跳b的距離，再第三次從上一次的位置往右跳a的距離…問(wèn)跳完k次的坐標(biāo)。
思路：直接算。
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
題意: 給出一個(gè)長(zhǎng)度為n(3 ≤ n ≤ 100)的數(shù)組，可能為1或者0，1表示這層亮燈，0表示沒(méi)亮燈。沒(méi)有亮燈的用戶會(huì)被亮燈的用戶打擾的條件是：他沒(méi)亮燈，但他的左右都亮著燈。現(xiàn)在要求讓所有人都不被打擾，求最少需要滅掉的燈的數(shù)量。
思路: 如果是“1 0 1 0 1”這樣的串，那么我們只需要關(guān)掉最中間的一個(gè)燈即可，故我的思路是記錄下所有0的位置，再模擬找是否存在這種連續(xù)的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
題意：給出一個(gè)長(zhǎng)度為n()的數(shù)組，我們稱一個(gè)數(shù)組“good”當(dāng)且僅當(dāng)刪掉這個(gè)數(shù)組中的一個(gè)數(shù)字之后，存在一個(gè)數(shù)等于其他數(shù)字的和，現(xiàn)在問(wèn)多少個(gè)數(shù)字單獨(dú)被刪掉后可以構(gòu)成“good”數(shù)組，并輸出這些被刪掉的數(shù)字的下標(biāo)（按任意順序輸出即可）。
思路：若一個(gè)數(shù)字是其他數(shù)字的和，那么就是說(shuō)sum/2這個(gè)數(shù)字一定存在。
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
題意：給出一個(gè)長(zhǎng)度為n的數(shù)組，現(xiàn)在要找一個(gè)長(zhǎng)度為k的數(shù)組，使得原數(shù)組減長(zhǎng)度為k的數(shù)組的次數(shù)盡量的多，并輸出這個(gè)長(zhǎng)度為k的數(shù)組。
