A Medium Number
题意
三个数，输出中位数。
思路
排序
input
9
5 2 6
14 3 4
20 2 1
1 2 3
11 19 12
10 8 20
6 20 3
4 1 3
19 8 4
output
5
4
2
2
12
10
6
3
8
代码
int n, m; int a[N]; void solve() { n = 3; for (int i = 0; i < 3; i++) cin >> a[i]; sort(a, a + 3); cout << a[1] << endl; }
B Atilla’s Favorite Problem
题意
找到最大字符，对应如下输出：‘a’ -> 1；‘b’ -> 2；…；‘z’ -> 26；
思路
维护最大值
input
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz
output
1
23
19
6
26
代码
int n, m; int a[N]; void solve() { int n; cin >> n; string s; cin >> s; int mx = -1; for (auto c: s) { mx = max(mx, (int)(c - 'a') + 1); } cout << mx << endl; }
C Advantage
题意
输出每个数 - 除自己之外的最大值。
思路
维护最大和次大，排序。
input
5
4
4 7 3 5
2
1 2
5
1 2 3 4 5
3
4 9 4
4
4 4 4 4
output
-3 2 -4 -2
-1 1
-4 -3 -2 -1 1
-5 5 -5
0 0 0 0
代码
int n, m; int a[N], b[N]; void solve() { int n; cin >> n; int x = -1, mx = -1; rep (i, 1, n) cin >> a[i], b[i] = a[i], x = max(x, a[i]); sort(b + 1, b + 1 + n); mx = b[n - 1]; rep (i, 1, n) if(a[i] == x) cout << x - mx << ' '; else cout << a[i] - x << ' '; cout << endl; }
D Challenging Valleys
题意
思路
如上条件，即一个 V 字型的尖尖，或者 _/ 的平段，或者 \_ 的平段。
统计这三种的个数，看是否最终为 1 即可。
便于统计，我们记数组 1−n，初始化a[0]=a[n+1]=INF。
双指针，左端点固定，去移动右端点，直到这一段相等结束（条件1），判断上述 V 字型条件（条件2，3）即可。
input
6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10
output
YES
YES
NO
YES
YES
NO
代码
int n, m; int a[N]; void solve() { cin >> n; rep (i, 1, n) cin >> a[i]; int cnt = 0; a[0] = a[n + 1] = mod; int l = 1; for (int i = 2; i <= n + 1; i++) { while (i <= n && a[i] == a[l]) i++; if (a[l] < a[l - 1] && a[i - 1] < a[i]) cnt++; l = i; } if (cnt == 1 || n == 1) cout << "YES" << endl; else cout << "NO" << endl; }
E Binary Inversions
题意
给你01字符串，问至多一次，反转一个字符（0-1,1-0），使得逆序对最大，输出最大个数。
思路
三种情况：
0次操作：
直接统计逆序数即可，维护后缀0的数量，一次遍历，累加上位1的0的贡献。
1次操作：
从前往后第一个0改1
从后往前第一个1改0
input
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1
output
3
7
1
13
2
代码
有点烂，不想改了，思路够清晰。
int n, m; int a[N]; void solve() { cin >> n; int res = 0; int zero = 0, one = 0; for (int i = 1; i <= n; i++) cin >> a[i], zero += 1 - a[i], one += a[i]; int xx = zero; for (int i = 1; i <= n; i++) if (a[i] == 1) res += xx; else xx -= 1; int idx1 = 1; while (idx1 <= n && a[idx1] == 1) idx1++; if(idx1 <= n && a[idx1] == 0) a[idx1] = 1, zero -= 1, one += 1; int t = zero, res1 = 0; for (int j = 1; j <= n; j++) if (a[j] == 1) res1 += t; else t -= 1; if(idx1 <= n && a[idx1] == 1) a[idx1] = 0, zero += 1, one -= 1; int res2 = 0, idx = n; while (idx >= 1 && a[idx] == 0) idx--; if (idx >= 1 && a[idx] == 1) one -= 1, zero += 1, a[idx] = 0; t = zero; for (int j = 1; j <= n; j++) if (a[j] == 1) res2 += t; else t -= 1; cout << max({res, res1, res2}) << endl;
F Quests
题意
给定 n ， c ， d n，c，dn，c，d，表示任务数组大小 n ， d n，dn，d 天要赚至少 c cc 元。每次工作了任务 i ii，那么接下来 k kk 天，这个任务不可再做。问 k kk 最大能是多少。
思路
最小的最大 ：二分答案
贪心的从大到小排序，维护前缀和。贪心的做任务获利高的任务，但每隔 k kk 天才做下一次，所以一个周期做 k + 1 k+1k+1 个任务（d dd 很大则考虑这种写法，否则直接暴力 d dd 天每次循环加上对应天下做的任务即可）。每次 c h e c k checkcheck 去判断，当前每个任务重做时间隔 k kk 天，且在 d dd 天内，能否获利 c cc 元。
input
6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1
output
2
Infinity
Impossible
1
12
0
代码
c h e c k 1 check1check1： 暴力加，循环节控制当天做的任务 i d idid。 c h e c k checkcheck： d dd 如果很大，则按周期加。 int n, m, c, d; int a[N], s[N]; bool check1(int x) { int res = 0; int now = 1; for (int i = 1; i <= d; i++) { if (now <= n) { res += a[now]; now++; } if (i % (x + 1) == 0) { now = 1; } } return res >= c; } bool check(int x) { x += 1; int pre = 0; if (x > n) pre = s[n]; else pre = s[x]; int now = 0, res = 0; while (now + x <= d) { res += pre; now += x; if (res >= c) return true; } for (int i = 1; i <= d - now && i <= n; i++) res += a[i]; return res >= c; } void solve() { cin >> n >> c >> d; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n, [=](int i, int j){ return i > j; }); int z = 0; for (int i = 1; i <= min(n, d); i++) z += a[i]; if (z >= c) { cout << "Infinity" << endl; return ; } if (d * a[1] < c) { cout << "Impossible" << endl; return ; } for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; int l = 0, r = 2e18; while (l < r) { int mid = (l + (r - l + 1) / 2); if (check(mid)) l = mid; else r = mid - 1; } cout << r << endl; }
G SlavicG’s Favorite Problem
题意
n 个点，n−1条边，边权 w i。（每走一边，需要异或当前边权）。给定 a,b，问从 a 出发，能否走往 b 点。条件是仅当走到 b 时，当前异或值为 0。并且，可以允许在路途中进行一次跳跃，即直接跳到任意除 b bb 外的一点。
注意的是，但凡走到了 b bb 就需要截止了（如果不为0，就走不到）。这意味着，从 a aa 开始走，要想去往 b bb 的子树下，仅能使用一次跳跃过去，而不能走过去。
思路
分别以 a , b a,ba,b 为根节点，计算所有点到根节点的一个前缀异或值，记 f a , f b fa,fbfa,fb 数组。（注意，这里 a aa 为根节点的话，不能去往 b bb 的子树）
对 f a fafa 数组，将所有可达点（f a [ i ] ! = − 1 fa[i] != -1fa[i]!=−1，包括 a aa 本身【因为如果 f b [ a ] = 0 fb[a]=0fb[a]=0 是直接可达的】，默认 f a [ a ] = 0 fa[a] = 0fa[a]=0）统计进 m a p mapmap 中。
对 f b fbfb 数组，遍历所有点，判断如果当前点不是 b bb 本身，且 m a p mapmap 中存在 f b [ i ] fb[i]fb[i] ，那么说明至多一次跳跃，可以让跳跃前异或值等于跳跃后异或值，走完到 b bb 即异或为 0 00。
input
3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5
output
YES
NO
YES
代码
int h[N], w[M], e[M], ne[M], idx; void add(int a, int b, int c = 1) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } int n, a, b; int fa[N], fb[N]; int root; void dfs(int u, int f, int v) { if(root == a) fa[u] = v; else if(root == b) fb[u] = v; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == f) continue; if (root == a && j == b) continue; dfs(j, u, v ^ w[i]); } } void solve() { memset(fa, -1, sizeof fa); memset(fb, -1, sizeof fb); memset(h, -1, sizeof h); cin >> n >> a >> b; for (int i = 0; i < n - 1;i ++) { int u, v, x; cin >> u >> v >> x; add(u, v, x), add(v, u, x); } root = a; fa[root] = 0; dfs(a, -1, 0); root = b; fb[root] = 0; dfs(b, -1, 0); map<int, int> mp; bool f = false; for (int i = 1; i <= n; i++) { if (i == b) continue; // 删掉也行吧，fa[b] == -1; else if(fa[i] != -1) mp[fa[i]] = 1; } for (int i = 1; i <= n; i++) { if (i == b) continue; else if (mp.count(fb[i])) f = true; } cout << (f ? "YES" : "NO") << endl; }
