带星号的表示 vp。
\(*\) CF Round 601 Div.1
做出 A 和 B1。
B2. Send Boxes to Alice (Hard Version)
考虑 \(a\) 的前缀和数列 \(S\)，在 \(a\) 中移动一个数，相当于在 \(S\) 中单点 \(\pm 1\)。并且 \(S_n\) 一定是不变的，且最终的公约数一定是 \(S_n\) 的约数。显然只需要枚举所有质数 \(p\mid S_n\)。并且“所有 \(S_i\) 都是 \(p\) 的倍数”与“所有 \(a_i\) 都是 \(p\) 的倍数”是等价的。
所以，显然答案就是 \(\sum_{i=1}^{n-1} \min(S_i\bmod p,p-(S_i\bmod p))\)，并且也可以保证 \(S_i\) 单调不减。时间复杂度 \(\mathcal{O}(n\omega(n))\)。
\(*\) CF Round 604 Div.1
做出 A，B，赛后五分钟做出 C。
B. Beautiful Sequence
首先将所有 \(0,2\) 按顺序排起来，得到 \(00\dots0022\dots22\) 这样的序列，然后有两种情况：
- 第一个 \(1\) 或 \(3\) 插入在开头；
- 第一个 \(1\) 或 \(3\) 插入在开头的后面一个位置。
分类讨论这两种情况，然后检查是否符合要求。
代码：https://codeforces.com/contest/1264/submission/157810494。
C. Beautiful Mirrors with queries
假如没有修改，设 \(f_i\) 为顺利通过 \(i\) 所需的期望步数，那么 \(f_i=p_i(f_{i-1}+1)+(1-p_i)(f_{i-1}+f_i+1)\)。解得 \(f_i=\frac{f_{i-1}+1}{p_i}\)，也即 \(f_i=\sum_{k=1}^i (\prod_{j=k}^i p_j)^{-1}\)。通过一点预处理，就能 \(\mathcal{O}(1)\) 求出通过一段区间的期望步数。
所以用 std::set 维护即可。
\(*\) CF Round 733 (Div.1 + Div.2)
做出 A ~ D，赛后做出 E。
D. Secret Santa
一开始写了个基环树 dp，还写错了。
首先，设 \(a\) 中不同的数字有 \(k\) 种，答案恰好可以取到 \(k\)。
设答案是 \(p_1,p_2,\dots,p_n\)，我们钦定任意 \(k\) 个位置 \(i_1,i_2,\dots,i_k\)，使得 \(a_{i_1},a_{i_2},\dots,a_{i_k}\) 两两不等，并使得这些位置的 \(p_{i_x}=a_{i_x}\)。记 \(b_1,b_2,\dots,b_{n-k}\) 表示此时还没确定 \(p\) 的位置，\(c_1,c_2,\dots,c_{n-k}\) 表示此时还没被使用的位置。
然后有两种情况：
- 假如 \(k=n-1\) 且 \(b_1=c_1\)，那么除 \(b_1\) 以外的所有元素形成了一个环，需要略微调整这个环使得 \(b_1\) 被 fulfilled。
- 否则，这里有一种有趣的做法：随机打乱 \(b_1,b_2,\dots,b_{n-k}\)，如果 \(\forall i,b_i\neq c_i\) 的话，就停止，否则再次打乱。这个过程期望只需要做 \(e\approx 3\) 次。
E. Minimax
分五种情况讨论。吐了。
Edu Round 129
做出 A ~ D。
\(*\) CF Round 606 Div.1
做出 ABC。
C. Beautiful Rectangle
设序列中 \(x\) 的出现次数是 \(c_x\)，有一个结论：设矩形大小为 \(h\times w\) 且 \(hw=n\)，假如 \(\max\limits_x \{c_x\}\le \min(h,w)\)，那么序列中的所有数都可以放在这个矩形中。
这是因为，在最坏形况下，所有数的出现次数都等于 \(\min(h,w)\)。不妨设 \(h<w\)，那么考虑如下形式的构造即可：
\[\begin{matrix} 1 & 2 & \dots & w-2 & w-1 & w\\ 2 & 3 & \dots & w-1 & w & 1\\ 3 & 4 & \dots & w & 1 & 2\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ \end{matrix} \]假如有一些数的出现次数 \(<\min(h,w)\)，那么可以钦定每 \(\min(h,w)\) 个为一组，并认为每组内的数相同。
所以枚举 \(h\times w\) 并找到 \(h\) 和 \(w\) 最接近的情况，对于 \(h\times w\) 最大、且所有数都可以放进去的方案，按照上面的方法构造即可。
代码。
\(*\) CF Round 609 Div.1
做出 A。
B. Domino for Young
将杨表黑白染色，可以发现一个多米诺骨牌恰好覆盖一个黑格和一个白格。设黑格的数量是 \(c_1\)，白格的数量是 \(c_2\)，答案的上界就是 \(\min(c_1,c_2)\)。
将相邻的黑格和白格连边，然后做二分图最大匹配。假如存在一个黑格 \(u\) 和一个白格 \(v\) 没有匹配，我们将二分图上 \(u\to v\) 的路径上的边全部取反，即可让它们匹配。所以答案就是 \(\min(c_1,c_2)\)。
CF Round 795 Div.2
做出 A ~ D。
E. Number of Groups
用并查集维护连通块。按照右端点从小到大处理每个线段。可以发现，对于每个连通块，我们只需要记录其中右端点最大的一个红色线段和一个蓝色线段。用两个 std::multiset 维护。
对于每一条线段，在 multiset 上二分找到所有与它有交的线段，然后逐一合并这些线段所在的连通块即可。注意区分 std::set 和 std::multiset。
代码。
CF Round 800 Div.1
做出 AB。
C. Keshi in Search of AmShZ
我为啥想不到。我为啥想不到。我为啥想不到。
设 \(D_u\) 为 \(u\to n\) 在最优策略下需要的天数，那么 \(D_u\) 就是没被 block 掉的 \((u,v)\) 的 \(\max D_v\)，加上被 block 掉的个数加一。
将所有边的方向反转然后 Dijkstra。开始时所有边都被 block 掉，每次从堆中取出一个点 \(u\)，并更新所有与 \(u\) 相连的 \(v\) 的答案。
假如固定一个点 \(u\) 并考虑 \(D_u\) 是如何被更新的，因为 Dijkstra 的过程中，取出的点的 \(D\) 单调不减，所以当前的 \(\max D_v\) 就是最新被取出的这个点的 \(D\)。对于那些没有被取出的边，它们一定会被 block。
代码。
CF Round 818 Div.2
做出 A ~ E。
Edu Round 135
做出 A ~ E。Performance 达到了 2500，并且上了 Master，可喜可贺。
CF Round 821 Div.2
做出 A ~ D2，Performance 2277。
E. Conveyor
考虑一组询问 \((t,x,y)\)：我们算出有多少个时间 \(t'\le t\) 使得在 \(t'\) 时间 \((x,y)\) 上有 slime，设这个数是 \(f(t,x,y)\)。假如 \(f(t,x,y)=f(t-1,x,y)\) 则答案为 Yes，否则为 No。
考虑这个 \(f(t,x,y)\) 怎么算。注意到任意两个 slime 都不可能重合，且前 \(\max(t-x-y+1,0)\) 个 slime 都有到达 \((x,y)\) 的可能性，因此在 \((0,0)\) 处放 \(\max(t-x-y+1,0)\) 个 slime，并 DP 算出有多少个到达了 \((x,y)\) 即可。
CF Round 822 Div.2
做出 A ~ E，Performance 2313。
E. Rectangular Congruence
假如我们构造出了一个矩阵 \(A\)，它除了对角线的限制不一定满足以外，其他限制均满足，那么对于所有 \(i\)，把第 \(i\) 行整体加上 \(b_i-A_{i,i}\) 就可以让 \(A\) 满足对角线的限制。
而满足限制的 \(A\) 是好构造的，例如 \(A_{i,j}=ij\bmod n\)。
F. Zeros and Ones
我终于学会数位 DP 的写法了，感动。
稍微推一下就可以得到，答案就是 \([0,m)\) 中整数 \(x\) 的个数，使得 \(\operatorname{popcount}(x)\not \equiv \operatorname{popcount}(x+n)\pmod 2\)。我们设 \(f_{i,j,k,lim}\) 表示考虑 \(x\) 的最低的 \(i\) 位，当前 \((\operatorname{popcount}(x)-\operatorname{popcount}(x+n))\bmod 2\) 的值是 \(j\)，计算 \(x+n\) 时从 \((i-1)\) 位到 \(i\) 位的进位是 \(k\)，\([x\ge m]\) 的真假是 \(lim\) 的 \(x\) 的个数。这样就可以转移了，时间复杂度 \(O(t\log n)\)。
f[0][0][0][1] = 1;
For(i, 0, B - 2) {
int ncur = (n >> i) & 1, mcur = (m >> i) & 1;
For(j, 0, 1) For(k, 0, 1) For(lim, 0, 1) {
For(x, 0, 1) f[i + 1][j ^ ncur ^ k][x + ncur + k > 1][x == mcur ? lim : (x > mcur)] += f[i][j][k][lim];
}
}
cout << f[B - 1][1][0][0] + f[B - 1][1][1][0] << '\n';