2024多校合集
牛客第一场rank 15
D所有后缀的 xor.
注意到任何后缀都可以用前缀和 $S_n - S_i$ 表示。
也就是我们可以用一个 $F(x) = \oplus (x-S_i)$ 来做这个答案。
考虑 $(x - S_i) \mod 2^{k+1}$ 的结果来做讨论 $2^k$ 这一位是 $1$ 还是 $0$。
转化为单点加法，区间求和的问题。
J考虑两维独立，只有左右边界，那么可以二分到第一个碰壁的位置，然后碰壁和碰壁之间可以倍增求解。
倍增的代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70133770
也可以类似 HoMaMa 一样:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70123888
1234567891011121314151617181920212223242526struct Fun { Int a, b, c, d; Int f(Int x) const ...
cf1996
A.先用 4 填，填不了用 2.
被 codeforces better 骗了，过了样例，A wa2
12345678void solve() { int N; cin >> N; int ANS = N / 4; if (N % 4 == 2) { ANS++; } cout << ANS << "\n";}
B.手动模拟.
123456789101112131415void solve() { int N; cin >> N; int K; cin >> K; vc<vi> A(N, vi(N)); rep(i, N) rep(j, N) { char c; cin >> c; A[i][j] = c - '0'; } for (int i = 0; i < N; i += K) { for (int j = 0; j & ...
post
感觉停更好久了，好多东西也没发，这里当做某个合集发吧。
cf1914
A-E 一眼。
F 是一个贪心，一一配对的话，那么如果有超过一半的，别的都能和他配对，然后再考虑剩下的部分，直接贪就好了，如果没有超过一半的，那么全都可以互相配对，就做完了。
G 是一个区间 xor hash。
cf1913
A. 模拟
B. 模拟
C. 贪心的从高到低取，二进制拆分一样的思路，能取就取。
D. 笛卡尔 dp。
https://codeforces.com/contest/1913/submission/238025170
E. 最小费用最大流。
我的建图方案是：考虑让流量是 n*m，这样刚好一一对应，然后就看一个点要不要改了。
https://codeforces.com/contest/1913/submission/238025260
cf1905
A. max(n, m)
B. (leaf+1)/2
C. 选出来的 t 每次减少 1。
https://codeforces.com/contest/1905/submission/238024495
D. 倍长之后，每次往后增加一个数，删掉开头的数字，区间取 max，区间求和，线段树二分。
E. 令 $f(n, p)$ 为有 n 个点，当前是 p 的答案，然后发现其实是一个类似二次函数的东西，递归就能维护了。
cf1904
vp 的，不是很行。
A.B. 略
C. 有点诈骗，发现三次以上肯定可以造出来一个 0。
D. 感觉有点难度，可以用单调栈之后，就变成区间取 max 的操作。
E.F. 板子题。
E. 是维护直径。
F. 是区间建图。
cf1907
没有速通的场。
G 题发现锁定基环树多出来的边之后方案唯一。
直接写就好了。
https://codeforces.com/contest/1907/submission/235936352
不想 dp 就能很快过了。
cf1902
模板题场。
E 字典树。
F 可持久化线性基。
https://codeforces.com/contest/1902/submission/235829632