[CF1586I] Omkar and Mosaic 题解
Getaway_Car
·
·
题解
下文中：
- 视题目中的两种颜色为黑色与白色。图示中所有颜色均只是为了表示颜色的相同或不同，且白色代表未填充。
- 记 (x, y) 表示第 x 行第 y 列的格子。
- 认为两个格子“相等”或“不等”，当且仅当两个格子的颜色相同或不同。
难点在于观察性质。
考虑在没有任何限制的情况下，一组合法解有哪些性质。有两个基本性质是：
- 位于角落的格子的颜色与其相邻的格子颜色相同。
- 对于一个不在边缘的格子，它的四联通中，恰好有 2 个黑色格子与 2 个白色格子。
初始我们没有进行任何涂色。
:::align{center}
:::
根据第一个性质，可以如下涂色。
:::align{center}
:::
根据第二个性质，可以不断扩展。
:::align{center}
:::
注意到，当 n 为奇数时，中间格子的颜色一定会产生冲突，所以 n 为奇数时一定不合法。
:::align{center}
:::
:::info[为什么]
对于主对角线，有 (4, 5) \ne (5, 6)；对于副对角线，有 (4, 5) = (5, 6)。
:::
依然是由于第二个性质，对于如图所示的这些斜列，每个斜列的颜色都是黑白交替的。图中只展示了一个方向的斜列，另一个方向同理。
:::align{center}
:::
:::info[为什么]
例如对于 (4, 2)，第二个性质要求 (3, 2), (4, 1), (4, 3), (5, 2) 中两黑两白，又因为 (3, 2) \ne (4, 3)，所以 (4, 1) \ne (5, 2)。
其余位置同理。
:::
考虑网格的一个角落，有 (1, 3) = (3, 1)，又有 (1, 3) = (1, 4), (3, 1) = (4, 1)，故有 (1, 3) = (1, 4), (3, 1) = (4, 1)。依此类推，我们可以得到两个重要结论：
- 网格关于主对角线与副对角线对称。
- 有 (1, 2x - 1) = (1, 2x)\ (x \in [1, \frac n 2])。
:::info[为什么 (1, 3) = (1, 4), (3, 1) = (4, 1)]
因为 (1, 2) \ne (2, 3)，为了让 (1, 3) 有两个相邻的格子与它颜色相同，我们只能让 (1, 4) 与它颜色相同。
:::
:::align{center}
:::
::::info[如何“依此类推”]
上图的下一步会变成：
:::align{center}
:::
在上图中，颜色是这样确定的：
- $(2, 5)$：因为 $(2, 3) \ne (3, 4)$，所以 $(1, 4) \ne (2, 5)$，也就是（部分）斜列颜色黑白交替的性质。
- $(5, 2)$：与 $(2, 5)$ 同理，且显然有 $(2, 5) = (5, 2)$。
- $(1, 6)$：与 $(1, 4)$ 同理，因为 $(1, 4) \ne (2, 5)$，所以 $(1, 5) = (1, 6)$。
- $(6, 1)$：与 $(1, 6)$ 同理，且显然有 $(1, 6) = (6, 1)$。
下一步会变成：
:::align{center}
:::
最后会变成：
:::align{center}
:::
最后这图只能当成乐子看。
::::
---
可以证明，上述条件是充要的。
考虑题目中给的限制。我们可以根据斜列与对称的关系，将所有限制都转化到第一行，再根据 $(1, 2x - 1) = (1, 2x)\ (x \in [1, \frac n 2])$ 尝试补全第一行。最后，若第一行被补全了，那么有唯一解；若第一行未被补全，那么有多解；若转化与补全过程中有矛盾，那么无解。
若有唯一解，再根据第一行推出整个网格即可。
代码是好写的，就不放了（实则是因为我的代码写得一坨）。