比赛地址：http://jzoj.net/senior/#contest/home/2821

水叮当的舞步

题面

考场

这个名字好熟悉。？

贪心一下？直接看看左上角所在的联通块外接的颜色中最多的然后去改那种颜色？先写了出来，发现不是一点难写。

手造数据发现好像贪心有问题。那么看外接颜色中联通块内个数之和最多的去改？发现过了手玩的样例。

感觉可以 $A$ 于是开始看后面的题。//打个暴力都好。 $orz..$

出分： $0pt..$ 多测清零之后 $10pt.$

贪心错了。 $orz.$ .

正解

搜索优化。。

首先最朴素的搜索：直接搜每一次跳什么颜色。

然后剪枝：

迭代加深，就是搜1层，2层…慢慢地搜下去。
如果剩下的部分中不同的颜色个数加上现在已经进行的操作个数已经超过了现在搜的层数直接减掉。

这样就可以 $A$ 了。

$code:$ https://paste.ubuntu.com/p/DXr5JSwKqd/

Vani和Cl2捉迷藏

题面

那么就是要求一个一般图的最大独立集。NP问题啊。。。

只能过20pt.的点。正解估计是什么神仙做法了。

出分：因为看错题爆零。

正解

好的，他就是一个 $DAG$ 然后那个互相望到的意思是一条路径上的前面的点可以看到后面的所有点。那就是在 $DAG$ 上的最大独立集了。然后就可以拆成入点和出点，做一个最小路径覆盖数 $cnt$ （就是最大匹配数），然后直接用 $n - cnt$ 就可以了。

二分图求一个最大匹配数直接匈牙利或者 $dinic$ 就可以了。//这是最简单的一题。。

$code:$ https://paste.ubuntu.com/p/RzNnpvkqdZ/

粉刷匠

题面

考场

容斥？不太行。暴力吧。看起来可以 $dp$ 然后想了好久发现最朴素的dp都要爆炸然后放弃了。

出分：暴力又没清零 $40pt => 30pt..$

正解

两个老师讲了两种，下面分别介绍。

两维比较简单的DP

考虑 $dp_{i, j}$ 表示已经选好了前 $i$ 种颜色，其中有 $j$ 对相邻的同色。

然后考虑转移，现在考虑怎么转移到 $dp_{i+1}$ 上去。首先需要把 $c_{i+1}$ 个桶分成 $k$ 组，然后再把这 $k$ 组插到前面的 $\sum_{a=1}^{i}c_{a}$ 的空里面。然后因为可能插进去之后把相邻同色的给破坏了，因此需要枚举一个 $t$ 表示有 $t$ 个相邻同色被破坏了。那么转移方程就可以写出来了：

$\Large dp_{i + 1, j + c_{i+1}-k-t} +=dp_{i, j} \times C_{c_{i+1}}^k \times C_k^t \times C_j^t$

然后就可以 $A$ 掉了。这个调起来是有点恶心的。

$code:$ https://paste.ubuntu.com/p/HWJrPTG566/

七维很暴力的DP

先咕吧。。