题解 AT2166 【[AGC006E] Rotate 3x3】

首先通过一堆判断先把显而易见的错误给判掉。（比如一列的数字不是连续的、要换到的列数当前列相差为奇数等）。 然后发现一个很重要的结论：**我们可以把任意隔着一列的两列同时颠倒**。这一部分的证明很多大佬都已经详细讲过了，所以我只讲发现这个结论之后应该怎么做。 这个结论有什么用呢？ 发现对于任意两个列数奇偶性相同的列，我们可以先通过旋转操作将他们转到只隔着一列的情况，然后再用这个结论将两列同时颠倒，然后再转回这两列原来的位置。也就是说，**我们可以通过上述操作让两个列数奇偶性相同的列同时颠倒**，记这种操作为 $\operatorname{flip}$。 那么当列的顺序已经排好了，只是有些列还是颠倒着的情况下，如果颠倒的奇数列有偶数个，我们就可以通过 $\operatorname{flip}$ 操作将这些奇数列全部颠倒回来。偶数列同理。 不妨设 $tot_0$ 表示：假设所有的偶数列中，有 $k$ 列是倒序的，然后取 $tot_0$ 为 $k$ 的奇偶性，即 $tot_0=k\bmod 2$；设 $tot_1$ 表示：假设所有的奇数列中，有 $k$ 列是倒序的，然后取 $tot_1$ 为 $k$ 的奇偶性，即 $tot_1=k\bmod 2$。 **那么只有当 $tot_0$ 和 $tot_1$ 都为 $0$ 时，即需要颠倒的奇数列和偶数列的数量都是偶数时，我们才能通过操作让所有的列颠倒回来。** **也就是说，在列的顺序排好的情况下，若 $tot_0$ 和 $tot_1$ 都为 $0$，就输出 ```Yes```，否则输出 ```No```。** **那么我们现在要做的就是找出一种方式让列的顺序排好，不用管每一列上下是否颠倒，但要同时维护 $tot_0$ 和 $tot_1$。** 设 $to_i$ 表示当前矩阵的第 $i$ 列原本应该在矩阵中的第几列，那么我们的目的就是让所有的 $to_i=i$。 然后考虑一次操作，我们要 $180\degree$ 旋转某一个 $3\times 3$ 的矩阵，不妨设这个矩阵的列数是从第 $a$ 列一直到第 $a+2$ 列，记这种操作叫 $\operatorname{rotate}(a)$。（下文中注意和 $\operatorname{flip}$ 区分） 那么进行一次操作，对于这个 $3\times 3$ 的矩阵来说，其实就是把第 $a$ 列和第 $a+2$ 列交换，然后再把第 $1$ 行和第 $3$ 列交换。 转化到 $tot$ 和 $to$ 的变化上来： 将第 $a$ 列与第 $a+2$ 列交换后：第 $a$ 列要去的列数由 $to_a$ 变成了 $to_{a+2}$，所以这个操作的实质就是交换 $to_a$ 和 $to_{a+2}$。 将第 $1$ 行和第 $3$ 行交换后：由于 $a$ 与 $a+2$ 奇偶性相同，所以 $tot_{a\bmod 2}$ 实际上没有变化，而第 $a+1$ 列被上下交换会导致 $tot_{(a+1)\bmod2}$ 取反。 更进一步：考虑交换第 $x$ 列 $A$ 和第 $y$ 列 $B$，其中 $x$、$y$ 奇偶性相同，并设 $x\bmod 2$ 为 $p$。 也就是说我们先通过 $\dfrac{(y-2)-x}{2}$次 $\operatorname{rotate}$ 操作将 $A$ 从第 $x$ 列转到第 $y-2$ 列，然后再旋转 $1$ 次让 $A$、$B$ 交换，即进行操作 $\operatorname{rotate}(y-2)$，然后再通过 $\dfrac{(y-2)-x}{2}$ 次 $\operatorname{rotate}$ 操作将 $B$ 从第 $y-2$ 列旋转到第 $x$ 列。 对于 $to$ 来说，发现操作的效果是交换 $to_x$ 和 $to_y$。 对于 $tot$ 来说，发现一共 $\operatorname{rotate}$ 了 $\dfrac{(y-2)-x}{2}+\dfrac{(y-2)-x}{2}+1=y-x-1$ 次，共奇数次。并且每次 $\operatorname{rotate}$ 都是让 $tot_{p\operatorname{xor}1}$ 取反，所以总的效果就是让 $tot_{p\operatorname{xor}1}$ 取反。 所以我们可以 $O(1)$ 处理出交换第 $x$ 列和第 $y$ 列后的变化，而且交换两列已经转化到交换 $to$ 上来了。 现在重新理一下我们要做的东西：给出一个初始序列 $a=to_1,to_2,\cdots,to_n$，给出一个目标序列 $b=1,2,\cdots,n$，然后现在每次可以交换任意两个数，问你怎么从 $a$ 序列变到 $b$ 序列。 ~~这不是 sb 题吗？（逃~~ 我们就通过把 $a$ 序列中的 $1$ 交换到第一个位置来，然后再把 $a$ 序列中的 $2$ 交换到第二个位置来……以此类推。 有些题解是通过置换的方法来实现将 $a$ 序列变成 $b$ 序列的，也可以，但其实想得太复杂了。 最后交换完判断一下 $tot_0$ 和 $tot_1$ 是否都为 $0$ 就好了。 时间复杂度 $O(n)$。 代码如下： ```cpp #include<bits/stdc++.h> #define N 100010 using namespace std; int n,a[4][N],to[N],where[N];//where[i]表示i在to中出现的位置，即满足to[where[i]]=i bool tot[2]; void fail() { puts("No"); exit(0); } int main() { scanf("%d",&n); for(int i=1;i<=3;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) { if((a[1][i]==a[2][i]-1&&a[2][i]+1==a[3][i]&&!(a[3][i]%3))||(a[1][i]==a[2][i]+1&&a[2][i]-1==a[3][i]&&!(a[1][i]%3))) { to[i]=(a[2][i]+1)/3; where[to[i]]=i; if((i-to[i])&1) fail(); if(a[1][i]>a[2][i]) tot[i&1]^=1; } else fail(); } for(int i=1;i<=n;i++) { if(i==where[i]) continue; where[to[i]]=where[i]; swap(to[i],to[where[i]]); tot[i&1^1]^=1; } if(tot[0]||tot[1]) puts("No"); else puts("Yes"); return 0; } ```