CF2207G Toothless

· · 题解

赛时切了，也是靠这题上黑红了。

读完题就感觉太经典了，感觉思路和 CF2057G.Secret Message 很像啊。

这个 \frac{2}{3}P 很容易联想到对网格图三染色，令其标号为 c_{i,j}=(i+j)\bmod 3。

考虑什么样的目标态是合法的，注意到所有被染黑的格子的导出子图必须是森林，其所有树的先序遍历就是其合法的染色顺序。

其次可以注意到：若只将标号不为 k(k\in \{0,1,2\}) 的格子染黑，其导出子图 G 是森林。

证明：首先 G 中每个点的度数不超过 2，那么 G 只能是一条链或者环。但是你注意到环是不可能出现的，因为每个点要不与其左/上的点有边，要不与其右/下的点有边，其形状呈现出一个阶梯状物。下面是一个 10\times 10 且将标号不为 2 的点标为 1 的图。

0 1 1 0 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0 1
1 0 1 1 0 1 1 0 1 1
0 1 1 0 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0 1
1 0 1 1 0 1 1 0 1 1
0 1 1 0 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0 1
1 0 1 1 0 1 1 0 1 1
0 1 1 0 1 1 0 1 1 0

现在来处理这个 needy 的点全选的限制，首先本题保证有解，故所有 needy 的点的导出子图是森林。

由于 P 是非 needy 的点的价值之和，所以还是要把 needy 和非 needy 的点分开看。（注意 needy 的点也有其价值为 a）。

考虑枚举 k，将点分为两类：

1.所有 needy 的点构成点集 S。

2.所有标号不为 k 的非 needy 的点构成点集 T。

由于两者直接合并起来可能会产生环，所以需要删除一些 T 中的点。但是怎么删点还需要进行考虑。

题中给了一个关键性质：It is guaranteed that no needy cell is adjacent to a special cell.

也就是说 needy 点的周围全是价值为 a 的点，于是可以考虑加入 S 中的点后若不合法去删掉点集 T 中的点。

首先需要约束一下加入点集 S 的顺序，先加入标号不为 k 的点，再加入标号为 k 的点，显然，根据最开始的性质，加入标号不为 k 的点不会形成环，而加入标号为 k 的点后若形成环，则删掉一个与其相连的普通点。

我们断言：枚举 k，一定存在一个合法的 k 满足最后选择的点的代价之和大于等于 \frac{2}{3}P。

证明：先考虑量化一个 k 的价值，那就是 P-cost_k-del_ka+Qa，其中 cost_k 表示标号为 k 的非 needy 点的价值之和，del_k 表示途中删除的普通点个数，Q 表示初始 needy 点的个数。

若一个 k 满足条件则 P-cost_k-del_ka+Qa\ge \frac{2}{3}P，化简得 \frac{1}{3}P+Qa\ge cost_k+del_ka。注意到若能证明 \sum_{k=1}^3 cost_k+del_ka\le P+3Qa，那么根据抽屉原理就证明完了。\sum_{k=1}^3 cost_k=P，而 \sum_{k=1}^3 del_ka 其实是容易进行估计的，由于只有在加入标号为 k 的点时构成环，而在加入一个点时，加入其第一条边不会形成环，接下来加入其剩下的三条边最多形成 3 个环，故 del_k\le 3q_k，其中 q_k 表示标号为 k 的 needy 点个数。不过似乎可以分析到更紧的界？

于是本题就做完了，代码非常好写，就不放了，可以写成 \mathcal{O}(n^2m^2)，或者 \mathcal{O}(nm\alpha(nm))。