A

杜老师做的，听说是烂题。

B

签到题，先咕了。

C

做法一

倒过来模拟染色过程，考察联通块数的变化量。可以发现，倒过来模拟这个过程时，右边界有相同的颜色，下边界也有相同的颜色，所以染色会增加连通块当且仅当新的颜色与右边界和下边界都不同。

容易想到用线段树维护 DDP，每个节点要记录 $2^2$ 个值，表示不翻转/翻转行，不翻转/翻转列时的 DDP 状态。维护是简单的。

时间复杂度 $O(n\log n)$，有 $36$ 的常数，能跑过去。

做法二

先咕着。

D

不是我做的，咕了。

E

存在一个暴力的费用流做最小权完美匹配的做法，用 Cost Scaling 和匈牙利可以做到 $O(n^3\log V)$，常数比较大，应该是过不去的。

分析菱形覆盖的形态，发现对于上半部分，第 $i$ 行与第 $i+1$ 行间的竖直菱形数量恰好为 $i$，且相邻两层间的竖直菱形插空分布。于是可以把竖直菱形按照斜向分组，建出一个新的费用流，每一组对应 $1$ 的流量。此时只需限制点的流量和边的流量 $\leq 1$ 就可以保证竖直菱形插空分布。分类讨论一下边权的值暴力跑费用流。

注意到这个新图流量只有 $O(n)$ 大小，于是跑暴力即可，时间复杂度 $O(n^3\log n)$，可以通过。

F

签到题，求出每一层的 SG 函数，异或起来就做完了。

G

签到题，二分答案之后排序来 check 即可。

H

还没完全会，等过了再补。

I

杜老师做的签到题。

J

容易发现 $(1,0),(0,1),(-1,-1)$ 可以构造所有点，故答案 $\leq 3$。先特判答案为 $1$ 的情况。

要让答案 $\leq 2$，至少需要所有点在同一个半平面内。此时需要特判如果存在两个点方向恰好相反，如果还有不在直线上的点就答案为 $3$，否则答案为 $2$。

然后对于所有点在同一个半平面内的情形构造。对于所有点都 $x\geq 0$ 的情形，可以构造 $(0,1)$ 和 $(1,-10^{18})$ 作为答案。类比到所有情形，只需要半平面对应的直线的一个方向选择一个向量，然后找到半平面内尽量接近直线的点，往另一个方向拉到无穷远处即可。

尽量接近直线的点可以 exgcd 求出。

时间复杂度 $O(n+\log V)$。

K

可以建出一个差分约束模型，于是可以得到如果有解，那么存在一种方案每个点的值要么是 $0$ 要么是 $K$。

对于两个有包含关系的区间，可以确定大区间减去小区间的部分全是 $0$，并删除大区间。得到一个位置是 $0$ 之后需要把剩余的区间缩起来然后继续考虑包含关系，同时判掉区间被删空的情形。

对于不存在包含关心的情形，排序之后贪心即可，一定有解。

时间复杂度 $O(n\log n)$。需要注意实现的细节。

L

树上背包模板。

M

将代价拆到每条边上，变成 这条边交换的次数 $+$ 这条边两侧均出现了的颜色种类数。如果不进行交换，一条边的代价 $\leq 2$。对于初始存在一条边代价为 $0$ 的情形，显然取到理论最小值 $n-2$，特判即可。

然后可以发现，要让一条初始为 $2$ 代价的边变成 $1$ 代价，必须要用它进行一次交换，并且最终它恰好隔开黑色和白色。于是这样的边最多一条，只需要判这种边存不存在。

容易发现存在的充要条件是这条边：

1. 将树分成了两个区域，大小分别是黑色点个数和白色点个数。
2. 黑色区域有恰好一个白点。
3. 白色区域有恰好一个黑点。
4. 这个黑点与这个白点都不是叶子。

判断这四个条件即可，时间复杂度 $O(n)$。