Codeforces Round 1078 (Div. 2)

A

贪心。每删除 $k-1$ 个栅栏必须留下一个。答案为 $\lfloor \frac{n}{k}\rfloor(k-1)+n\mod k$。

B

假设我们已经确定了最后把钱放在哪个银行，对于其余的银行 $i$，除了 $a_i \mod x$ 余下的钱都是可以被转移到最后那个银行去的。枚举即可。

为什么 $a_i \mod x$ 的余数不能被转移？假设我们为了转移这个余数 $k$，将另外 $c_0$ 笔钱移过来，凑好了一些钱，转移了 $c_1$ 次到最后的目标银行里。那么这个过程中凑到这个银行里的钱数就是 $c_0\cdot y+k$，转出的钱数是 $c_1\cdot x$，最后对答案的贡献是 $c_1\cdot y$。如果 $c_1<c_0$，那这个过程是劣的，不如直接把钱转到最后的银行里。而 $c_0\leq c_1,y\leq x,k<x$ 与 $c_0\cdot y+k\geq c_1\cdot x$ 矛盾。因此这个结论是正确的。

C

模拟。先预处理 $10^5$ 以内的因数。从小到大枚举答案 $len$，枚举成功就退出。令 $s_i$ 为输入的第 $i$ 个字符串。令 $S_i$ 为 $\bigcup\limits_{j=1}^{k}\{s_{j,i}\}$，即所有 $k$ 个字符串在下标 $i$（字符串的下标从 $0$ 开始）的字符组成的集合。$cnt=\frac{n}{len}$。$len$ 作为答案合法的条件是 $\forall p\in [0,len),\bigcap\limits_{i\mod len=p}S_i≠\varnothing$。可以用位运算实现。

D

令被划分到左下部分的位置的和为 $w$，矩阵的总和为 $s$，则答案为 $w(s-w)=-w^2+sw$，在 $w=\lfloor\frac{s}{2}\rfloor$ 或 $\lceil\frac{s}{2}\rceil$ 处取到最大值。把这个最优的 $w$ 求出来。我们直接从下往上遍历行，一行里从左往右遍历列，找出在哪个位置 $(i,j)$，第 $i$ 行里 $j$ 及其左边的和加上第 $i+1$ 行下面的所有行的和正好是 $w$。这个位置一定存在。然后模拟输出方案即可。

E

以左上角为起点，右下角为终点 dp 一次，记为 $f_{i,j}$；以右下角为起点，左上角为终点 dp 一次，记为 $g_{i,j}$。然后考虑枚举对哪个位置取反。发现此时的答案是可以用 $f$ 和 $g$ 拼起来表示的。

如果枚举到图里的红色位置，那么不经过红色位置的答案可以用图里蓝色圆圈位置的 $f$ 和绿色方框位置的 $g$ 拼起来，经过红色位置的答案可以用红色位置的 $f$ 和 $g$ 叠加，再减去三倍的红色位置的值。处理一下前者的前缀和后缀最大值，再对所有答案取个 $\min$。需要注意边界。

qq 群里群友教了一个高手的实现：可以不用钦定是否经过跟红色位置在一行的位置，转而钦定经过跟它在一条斜线上的位置。边界情况少很多。

F1

考虑暴力的（有一维是异或和）的 dp 状态 $f_{u,x}$。它应该代表什么？在某个点 $u$ 继承子树状态的时候，我们当然想知道 $u$ 所属的连通块目前的异或和是多少，状态里的 $x$ 自然就代表这个值。如果 $v$ 是 $u$ 的儿子，从 $f_{v,y}$ 转移到 $f_{u,x}$ 的转移自然就分是否断开 $(u,v)$ 两种，如果不断开则是 $f_{u,x}\leftarrow f_{v,y}\cdot f_{u,x\oplus y}$，断开则是 $f_{u,x}\leftarrow f_{v,y}[y\in b]\cdot f_{u,x}$。这个暴力的复杂度是 $\mathcal{O}(nV^2)$。

发现 $k$ 很小，考虑把值域维度优化为与 $2^k$ 相关，将直接把值放在状态里换成用集合 $b$ 里的元素状态来表示值，将复杂度优化到 $\mathcal{O}(4^kn)$。令 $w_S=\bigoplus\limits_{i\in S}b_i$。

• 能否直接用 $f_{u,S}$ 表示原来的 $f_{u,w_S}$？我们发现，这样表示的瓶颈在于当一个连通块还没完全形成时，它的异或和并不一定能够被某个 $w_S$ 表示。
• 考虑不记录当前连通块的值，而是记录当前所有已经被切掉的子树的异或和。由于每个被切掉的子树的异或和都属于 $b$，这些异或和的异或和一定可以被 $w_S$ 表示！这样我们就得到了正确的状态设计，像暴力那样转移即可。实现时注意有些 $S$ 异或出来的结果可能是相同的，需要判一下。