今天题还算改的顺利

然后尝试简单DP

发现打不出来

（野兽先辈的嚎叫~）

[A]

是top_sort，但是被硬控。
就是把两个人的关系看做一个点，然后依次加边，做一遍topsort后如果不合法输出-1，否则按题意进行模拟，记 st[] 数组为当前每个人能面积的最早时间，模拟即可。

[B]

什么可爱的构造

什么难用的spj

所以我魔改SPJ调出了挂的那一个点算不算作弊（bushi

但是代价就是两个小时全部都放在这题上了。

很显然似乎操作数 \leq nm 的范围一定是给大的，因此我们可以先考虑将前面的 n-2 行，前 m-2 列全部清零，只留下右下角 2×2 的正方形。

对于那个正方形直接分类讨论做法就可以了。

[C]

警告：本题需要使用随机化。

不是konata你刚讲完就考啊

本来还以为应该是用主席树或者什么东西套一下的……

注意到 k\leq 5，而 n 却非常的大，这不禁让我们思考能不能通过某种方法让这个 k 派上用场。

再考虑第二档部分分的做法，由于所有颜色均 \leq k，因此可以状态压缩DP，记 f_{u,S} 为当前节点选择颜色的状态，有方程式 f[u][S]=min(f[u][S],f[u][T]+f[j][S\oplus T])，其中 T 是 S 的子集， j 是 u 的儿子。

然后嘛……我们用随机化暴力将 1-n 的颜色映射到 1-k，重复以上过程。

实在是太妙了！

当然如果你想在比赛中获得很高的部分分，你只需要输出 k 就可以了。

学生们只需要做题就可以了，可是出题人想的就多了。

[D]

我打的什么随机化+2-SAT

注意到每一匹马相互的憎恨数不超过 3。

我们分情况考虑。

最初我们假设所有马都在同一集合内，然后每次挑出不合法的马，将其扔进另一集合。

我们发现，无论其是否合法，相互的憎恨数量都减少了 1。

因此我们重复以上过程就可以了。

果然我没有独立思考能力。