主要思路
这个题有点 nb。
按道理来讲直接做第二问得要 \(\Theta(n^4)\) 的时间，而且看上去也没有什么搞头。我们考虑处理出所有的接壤位置 \( (x, y, c_a, c_y) \) 代表颜色为 \(c_x\) 、编号 \(x\) 的点和颜色为 \(c_y\) 、编号 \(y\) 的点接壤。这样的接壤位置只有 \(\Theta(n^2)\) 个，所以我们分类出来之后再用并查集搞即可。
上下界网络流
Codeforces 704D:Captain America – 题解
主要思路
一道比较板的上下界网络流。先考虑 \( red > blue \) 的情况，我们把所有点染成红色的然后再做个最大替换即可。我们考虑对每个点、每个横坐标、每个纵坐标做一个点，横坐标和源点、纵坐标和汇点的边需要大概算一下，得出流量范围 \(\frac{cnt_x}{2} \leq flow \leq \frac{d + cnt_x}{2}\)。得出这个范围之后就用板子套一下即可。
「Fortuna OJ」Apr 19 省选 A 组 – 解题报告
「Fortuna OJ」Apr 15 省选组 – 解题报告
A – 楼房搭建
首先这题的 \(\Theta(n^3)\) 是很好写的，如果要写到 \(\Theta(n^2)\) 的分，我们可以观察到 DP 的过程其实是一个做后缀 min 的过程，所以优化完毕（当然也可以线性规划，但是很难写）。
「BZOJ5451 / QuestOJ 2152」字符串 – 题解
主要思路
这题还是蛮有意思，有一些奇怪的细节。
首先，只考虑正串，我们就直接塞进 AC 自动机里做套路 DP 即可。考虑串在后半段的情况，发现其实你只要刻画好前半段后半段即可被自动刻画，所以我们做串的反串并把字符取反塞到正串的 AC 自动机里就可以让字符串出现在后半段。