【解题报告】Codeforces Round #743 (Div. 1)

赛时 $\tt{AB}$，$\text{rank 101}$。
改题 $\tt{CDEF}$。

属于是这个 $\tt{B}$ 在 $\text{Grandmaster}$ 计划里所以快速过了，然后被罚坐了/qd。

C. Paint

考虑区间 $\text{dp}$，简单的想法是设 $\text{dp}_{l,r,c}$ 表示将 $[l,r]$ 变成颜色 $c$ 的最小步数。复杂度太高，考虑观察性质。

可以通过归纳证明，将 $[l,r]$ 变成颜色 $c_r$ 是最优的。于是状态变成 $\text{dp}_{l,r}$ 表示将 $[l,r]$ 变为颜色 $c_r$ 的最小步数。

考虑如何使用“每种颜色的位置只有 $20$ 个”的条件，大胆猜想在枚举分割点的时候，只有与右端点颜色相同的位置才是有用的，实际上确实如此，因为其他情况下还需要一步才能使得区间相等。当然还需要特殊判断左右拓展恰好一个的情况。因此复杂度是 $\mathcal{O}(20n^2)$。

实际上就是 $\text{popcount}(i\oplus j)=1$，则 $i,j$ 连边。显然这是一张二分图（$\text{popcount}$ 奇偶性），所以这是一个类似二分图最大权匹配的问题。

注意到能跑的流量很小，考虑从这上面来优化。当选择了一组 $i,j$，则将有 $2(n-1)+1$ 组匹配被禁用（所有与 $i,j$ 相关的匹配），则最后只会禁用 $k\times (2(n-1)+1)$ 组。

这意味着每 $k\times (2(n-1)+1)+1$ 个匹配中，至少能选出一个大小为 $k$ 的匹配。因此显然最后的答案只会出现在权值最大的 $k\times (2(n-1)+1)+1$ 个匹配中。把他们拉出来跑费用流即可。找前若干大的匹配可以使用 nth_element 进行优化。

最大化最小部分的面积，先二分答案。然后对这种多边形划分问题，显然要考虑区间 $\text{dp}$。

这个 $\text{dp}$ 需要解决两个问题：

注意到我们在保证一个区间 $[l,r]$ 代表的多边形最外侧的面积 $\le$ 二分的面积的前提下，使得操作次数尽量小就行了——因为不管怎么样，只需要再砍一刀就一定满足条件。

直接转移，$\mathcal{O}(n^3\log V)$。

感觉这题挺生硬的......

先鸽。