CF1844E Great Grids 题解

· · 个人记录

写一下一个可能与众不同的做法。

假设已经确定了第一行，接下来依次确定每一行。实际上不难发现只要确定了第一个元素就能确定一整行。

继续观察。尝试构造一下就会发现实际上每一行都是同构的。这里同构指的是行间构成类似凯撒密码的移位关系，例如 ABC,BCA,CAB 是同构的。

继续找性质。由于一个串移动三位还是它本身，所以只有移动一位或两位是有效的。

为了方便理解，不妨假设原串为 ABCBAC，分别画出下一行接其两种不同同构串的结果：

显然对于每个 2 \times 2 的小矩形必然有一条对角线相等，不妨将这条对角线连起来。然后从绿点的视角观察这些线，发现对于所有对应的绿点，两种方案连出的线方向必然不同。

所以不同的行间关系仅有两种，而且两种互斥。不仅如此，我们可以构造出所有我们需要的行间关系，具体的话考虑增量构造即可。

我们把所有 n-1 个行间关系抽出来。由于本质不同的行间关系只有两种且互斥，所以如果两个行间关系只要存在一条连线相同就必然相同，如果存在一条连线不同就必然不同。

于是我们将所有相同的行间关系用并查集合并起来。接下来我们忽视这些边，仅考虑互斥行间关系的边。如果同一个连通块内有连边显然非法。否则连边一定存在于连通块间。将连通块缩起来后判断新图是否为二分图即可，容易证明这是充分必要的。

就具体实现来讲，注意到 k 很小，我们可以 O(k^2) 枚举一对限制。如果这对限制处于相互对应位置就进行处理，否则不处理。这部分复杂度是 O(k^2 \alpha(n)) 或 O(k^2 \log n) 的，视并查集具体实现而定。

接下来判断一下连通块内是否有边，有就说明非法。然后仅保留表示互斥行间关系的边，跑一下二分图染色即可。

时间复杂度 O(k^2 \alpha(n))。