A - A?C
#include <bits/stdc++.h> #define ll long long using namespace std; char s[5]; int main() { scanf("%s",s); if(s[1] == 'B') s[1] = 'R'; else s[1] = 'B'; printf("%s\n", s); return 0; }A.cpp
B - Trick or Treat
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 105; bool vis[N]; int main() { int n ,k; scanf("%d%d", &n, &k); for(int i = 0, x, y; i < k; i++) { scanf("%d", &x); for(int j = 0; j < x; j++) { scanf("%d", &y); vis[y] = true; } } int ans = 0; for(int i = 1; i <= n; i++) { if(!vis[i]) ans++; } printf("%d\n", ans); return 0; }B.cpp
C - Peaks
题意:有N个人,M条边,每个人有一个高度H,输出有多少个节点满足它比所有它相邻的人高。
数据范围:$ 2 \leq N \leq 10^{5}, 1 \leq M \leq 10^{5}, 1 \leq H_{i} \leq 10^{9} $
题解:开一个数组表示是否有它相邻的人比它高,每输入一条边更新即可。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5 + 5; bool vis[N]; int h[N]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &h[i]); } for(int i = 0, u, v; i < m; i++) { scanf("%d%d", &u, &v); if(h[u] <= h[v]) vis[u] = true; if(h[v] <= h[u]) vis[v] = true; } int ans = 0; for(int i = 1; i <= n; i++) { if(!vis[i]) ans++; } printf("%d\n", ans); return 0; }C.cpp
D - I hate Factorization
题意:给定X,输出一组(A,B),满足A5-B5=X。
数据范围:$ 1 \leq X \leq 10^{9} $
题解:枚举A,判断A5-X是否能正好开5次方即可。
#include <bits/stdc++.h> #define ll long long using namespace std; ll cal(ll x) { return x * x * x * x * x; } int main() { ll x; scanf("%lld", &x); for(ll a = 1;; a++) { ll det = cal(a) - x, bb = -1; for(ll b = 0;; b++) { ll t = cal(b); if(t == abs(det)) { bb = b; break; } if(t > abs(det)) { break; } } if(bb != -1) { printf("%lld %lld\n", a, bb * (det < 0 ? -1 : 1)); break; } } return 0; }D.cpp
E - This Message Will Self-Destruct in 5s
题意:给一个长度为N的序列A,求有多少数字对(i,j)满足Ai+Aj=|i - j|。
数据范围:$ 2 \leq N \leq 2 \times 10^{5} , 1 \leq A_{i} \leq 10^{9}$
题解:对于每个位置,每次找在它之前满足要求的数,即求有多少数字对(i,j)满足Ai+Aj=i - j(i > j)。
原式等价于:Aj + j = i - Ai,那么只需要每次查询 i - Ai的个数,然后更新Ai + i即可。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 5; int a[N]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } ll ans = 0; unordered_map<int, int> ma; for(int i = 1; i <= n; i++) { if(ma.count(i - a[i])) { ans += ma[i - a[i]]; } ma[i + a[i]]++; } printf("%lld\n", ans); return 0; }E.cpp
F - Three Variables Game
题意:给N个字符串("AB","AC","BC")和A,B,C三个值,按顺序执行每个字符串的操作,如果这个字符串是"AB",那么将执行A--,B++或A++,B--,其它字符串类似,并且每一个操作之后A,B,C三个值不能小于0,判断是否按顺序执行下来,如是,并要求具体操作序列。
数据范围:$ 1 \leq N \leq 10^{5}, 0 \leq A,B,C \leq 10^{9} $
题解:对于操作"AB":
1.A>B,那么就执行A--,B++。
2.A<B,那么就执行A++,B--。
3.A=B,看下一个字符串是否包含A,如果包含A,那就执行A++,B--,反之执行A--,B++。
其它操作类似(虽然没有证明这个做法的正确性,但是感觉很对。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5 + 5; char s[N][3]; int a[3], n; int main() { scanf("%d%d%d%d", &n, &a[0], &a[1], &a[2]); for(int i = 0; i < n; i++) { scanf("%s", s[i]); } vector<char> ans; bool flag = true; for(int i = 0; i < n; i++) { int ta = s[i][0] - 'A', tb = s[i][1] - 'A'; if(a[ta] > a[tb]) { ans.push_back(s[i][1]); a[tb]++, a[ta]--; }else if(a[tb] > a[ta]){ ans.push_back(s[i][0]); a[ta]++, a[tb]--; }else { if(a[ta] == 0) { flag = false; break; } if(i + 1 >= n || s[i][0] == s[i + 1][0] || s[i][0] == s[i + 1][1]) { ans.push_back(s[i][0]); a[ta]++, a[tb]--; }else { ans.push_back(s[i][1]); a[tb]++, a[ta]--; } } } if(flag) { printf("Yes\n"); for(int i = 0; i < n; i++) { printf("%c\n", ans[i]); } }else { printf("No\n"); } return 0; }F.cpp