题解：CF1887E Good Colorings

· · 题解

想了好长时间才会了证明为什么一定有解。（假设一开始全部染好了）

大概就是我归纳 n\times m 的网格染成至少 n+m 种颜色，一定有解。

考虑任意取出来一行，如果这样一种颜色的个数 \le 1，这样一种颜色仅在这一行出现，那么我直接删除这一行就可以应用归纳假设。

如果大于等于 2 了，我取出来这对应的两列，那因为我不能有矩形异色，所以这两列除了这两个位置，应该是完全相同的。

那我对于其中一列，有且仅有一种颜色，仅在这一列出现。所以归纳假设就好。

以上论证可能和正解没有必然联系。

但是可能启示了一些，找到每行每列有且仅有两个涂了色的格子的行列组。

你考虑如果找到了（一定能找到），你可以对于每个格子，向行与之相同和列与之相同的格子连边。

这样出现一些环。（不连通取其中一个就好）

然后考虑你将环（环长一定为偶数）分成两个相近的奇数长度，添加一个断点。

这样就可以恰好使得环长减半。没了。

然后说一下怎么找【每行每列有且仅有两个涂了色的格子的行列组】。

我的做法是，你现在原网格上，每个点朝四个方向最近的点连边，然后找到一个环，再缩掉中间类似

 x
 |
 x----x-----x

中间的那个点。

但是可能会出现一个“几”字型，重复走到了同一行。

那你在找环的时候你优先 DFS 和上一步方向相同的就可以规避共线的情形。

另一种方法是教练的，细节较少。

考虑每次删掉一个仅有一个数的行或列。

如果有空行，删掉她的同时任意删掉一个涂色点。

这样留下来的恰好是行列颜色数都等于 2 的。（因为总是保证了颜色数 c=n+m）

综上，操作次数不超过 10，复杂度 O(tn\log n)。