Codeforces Round 859 (Div. 4) A - D + F - G2 题解

A. Plus or Minus（800 分难度）

思路： 直接 if - else 判断。
参考代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){int a, b, c;cin >> a >> b >> c;if(a + b == c){cout << '+' << endl;}else cout << '-' << endl;return ;
}
int main(){int T = 1;cin >> T;while(T --){solve();}return 0;
}

B. Grab the Candies（800 分难度）

思路： 直接判断偶数和是否大于奇数和即可。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
void solve(){int n;cin >> n;int sum1 = 0, sum2 = 0;for(int i = 1; i <= n; i ++){cin >> a[i];if(a[i] % 2 == 0) sum1 += a[i];else{sum2 += a[i];}}if(sum1 > sum2){cout << "YES" << endl;}else cout << "NO" << endl;return ;
}
int main(){int T = 1;cin >> T;while(T --){solve();}return 0;
}

C. Find and Replace（800 分难度）

思路： 模拟即可。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int cnt[N];
bool check(string s, int st){for(char i = 'a'; i <= 'z'; i ++){cnt[i] = 0;}cnt[s[0]] = st;for(int i = 1; i < s.size(); i ++){if(cnt[s[i]] == 0){cnt[s[i]] = 3 - cnt[s[i - 1]];}else if(cnt[s[i]] == cnt[s[i - 1]]){return false;}}return true;
}
void solve(){int n;cin >> n;string s;cin >> s;if(check(s, 1) || check(s, 2)){cout << "YES" << endl;}else cout << "NO" << endl;return ;
}
int main(){int T = 1;cin >> T;while(T --){solve();}return 0;
}

D. Odd Queries （900 分难度）

思路： 前缀和相关的水题。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
long long s[N];
void solve(){int n, q;cin >> n >> q;for(int i = 1; i <= n; i ++){cin >> a[i];s[i] = s[i - 1] + a[i];}while(q --){int l, r, x;cin >> l >> r >> x;long long ans = x * (r - l  + 1) - (s[r] - s[l - 1]) + s[n];if(ans % 2){cout << "YES" << endl;}else cout << "NO" << endl;}return ;
}
int main(){int T = 1;cin >> T;while(T --){solve();}return 0;
}

F. Bouncy Ball（1700 分难度）

思路： 本题如果很多地方思考不到位很容易越写越乱，思路捋清楚直接模拟即可。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int MA = 1e5 + 10;
void solve(){int n,m;cin >> n >> m;int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;string s;cin >> s;int dx = (s[0] == 'U'? -1 : 1);int dy = (s[1] == 'L'? -1 : 1);int cnt = 0;int ans = 0;while((x1 != x2 || y1 != y2) && cnt < MA) {ans += (x1 == 1 && dx == -1 || x1 == n && dx == 1 || y1 == 1 && dy == -1 || y1 == m && dy == 1);if(x1 == 1) dx = 1;if(x1 == n) dx = -1;if(y1 == 1) dy = 1;if(y1 == m) dy = -1;x1 += dx, y1 += dy, cnt ++;}cout << (cnt == MA ? -1 : ans) << endl;return ;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

G2. Teleporters (Hard Version)（1100 分难度）

思路： 容易发现规律，排完序后，每次新出现的数不可以超过前面所有元素的和。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve(){int n;cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i];if(n == 1){if(a[1] == 1){cout << "YES" << endl;return ;}else{cout << "NO" << endl;return ; }}sort(a + 1, a + 1 + n);long long range = 1;for(int i = 2; i <= n; i ++){if(a[i] > range){cout << "NO" << endl;return ;}range += a[i];}cout << "YES" << endl;return ;
}
int main(){int T = 1;cin >> T;while(T --){solve();}return 0;
}