Codeforces Round 1049 (Div. 2)

这场质量非常高。

A

我像区，我怎么卡 A 卡那么久。

睡眠不足会导致思路不清晰。这种题显然应该考虑所有位置不正确的字符。

对于一个在 \(0\) 位置上的 \(1\) 一定有一个与它未匹配的 \(0\)，考虑能否通过一次操作将它们归位。

对于操作我们显然应该选择一个未归位的 \(0\) 和前面的一个 \(1\)，组成 \(1x0\)，此时会发现中间的 \(x\) 无论选什么都能够将左右两边的 \(0, 1\) 归位，并且如果 \(x\) 本身未归位，不可能通过此次操作使 \(x\) 位得到正确的字符。

所以答案就是所有位置错误的 \(1\)，即 \(S_{1 \sim cnt_0}\) 中 \(1\) 出现的次数。

B

这个 \(B\) 应该放到 \(A\)。

考虑令 \(k\) 为 \(y\) 的位数，则题目等价于 \(x + y | x \times 10^k + y\)。自己做的时候直接注意到 \(y = 8x\) 了，补一个可以推理得到的思路。

考虑 \(x \times 10^k + y =x \times (10 ^ k - 1) + x + y\)，于是 \(x + y | x \times (10^k - 1)\)，注意到 \(9 | 10^k - 1\)，所以令 \(y = 8x\) 即可。

C

这个 C 也很好想。

观察一下样例会发现操作次数等于 \(1\)。首先显然不能不操作，这肯定不优。其次如果 A 的操作肯定是选择一个价值最高的操作，B 的操作只能复原 A 的操作。然而有 cost 的限制，B 越操作 A 越有钱。所以 B 只能结束游戏。

于是问题就变成了通过一次操作能增加的最大值。从 \(1 \to n\) 扫一遍，对于奇数位需求当前偶数位前缀最大 \(-a_i - i\)，对于偶数位需求当前奇数位前缀最大 \(a_i - i\)。

当然如果 \(a\) 已经最优，你也可以不对 \(a\) 序列本身进行改变，只需要根据 \(n\) 的奇偶性对于 \(1, n\) 或 \(1, n - 1\) 操作一次即可。

D

这个题按我这个做法特别比较难想。

考虑如果我们选择了两个段 \([l_i, r_i], [l_j, r_j]\)，我们一定希望新的段是 \([l_i, r_j]\)，得到贡献 \(r_j - l_i\)。

注意到对于 \(l_i + r_i \geq l_j + r_j\)，有 \(r_i - l_j \geq r_j - l_i\)。于是我们将段按照 \(l_i + r_i\) 排序。

先只考虑 \(n\) 为偶数的情况，显然应该选取前 \(\frac{n}{2}\) 大的做 \(r\)，其余的做 \(l\)。

对于奇数的情况，考虑枚举哪一段不被选，其余计算同偶数情况。由于可以通过前缀和优化，所以复杂度是 \(O(n)\) 的。

一个好想的做法：

设 \(A\) 为选定的 \(l\) 集合，\(B\) 为选定的 \(r\) 集合，满足 \(A \cap B = \emptyset\)。

则答案为 \(\sum_{i \in B} r_i - \sum_{i \in A} l_i = \sum_{i = 1}^n r_i - \sum_{i \in A}(l_i + r_i)\)。

所以减掉前 \(\frac{n}{2}\) 小的即可。

E

赛后补题。

博弈题，但是并非博弈论。

先考虑 E1，\(m = 2\) 的情况下显然可以直接状压每一位是什么然后转移。设 \(F_{i, S, 0/1}\) 表示当前剩下 \(i\) 个集合，状态为 \(S\)，是 \(A\) 下或是 \(B\) 下，最后得到的值。

对于 \(m \leq 1000000\) 的情况就比较智慧了。

我们考虑枚举 \(k\)，\(S\) 中 \(< k\) 的位为 \(0\)，反之为 \(1\)。设 \(F_{i, S, 0/1}\) 为最后 \(S\) 能否剩下一个 \(\geq k\) 的堆。

那么对于最后可能剩下 \(\geq k\) 的堆的方案数为：

\[\sum_{i = 0}^{n} \sum_{S = 0}^{2^n - 1} [\operatorname{popcount}(S) = i]F_{i, S, 0/1} (m - k+ 1)^i(k - 1)^{n - i} \]

最后计算贡献是只需要外层再循环一层 \(k\) 即可。原因是我们将正好为 \(x\) 的贡献拆到了 \(k \geq 1\) 到 \(k \geq x\) 中。