题解 AT2166 【[AGC006E] Rotate 3x3】

· · 题解

Solution

我一开始以为不能保持其他不变的情况下旋转上下...

首先上下一定与中间绑定在一起,奇偶行互不影响(除了造成上下翻转).

然后你发现是可以对相差1的两列同时进行上下翻转的(这个其他题解已经讲得很清楚了)，于是就变成了一个上下颠倒个数的奇偶性问题.

因为只考虑奇偶,所以不管你怎么做,只要先按第二行排好列,再考虑上下颠倒列数的奇偶性.

那么有一个很暴力的想法:\ 我们尝试将给定序列转回原序列.\ 设给定的矩阵中第i列第二行的值为x,则to[i]=x,即第i位第二行现在的数是x。\ 记录当前奇、偶数列中上下颠倒列数的奇偶性为t[0]、t[1]。

枚举1到n,若i\neqto[i],不断swap(to[i],to[to[i]])(交换i行与to[i]行的数),每次swap使

t[i&1^1]^=1

(即奇偶不同的那一行上下颠倒行数的奇偶性变化)\ 最后检查t[0]和t[1]是否都为0即可。

这样做不仅是对的，还是O(n) 的。

证明如下:

我们发现to[i]没有重复元素且1~n中的所有元素均出现在to[i]中,那么我们可以将to[i]看作一个置换。

置换的循环表示：百度百科:循环

根据置换在循环上的定义，我们可以通过不断让i=to[i] 的方式让i重新回到i。\ 设经过的过程为a_1->a_2->...->a_{k-1}->a_k->a_1\ 那么有循环(a_1,a_2,...,a_k,a_1)\ 若该循环包含了1到n所有元素，则枚举停止。否则从余下的元素中任一元素开始，如上述方法进行，再得一循环，如此反复直到所有元素都取完为止。 可以发现上述过程只经过n个点，时间复杂度为O(n)。

而我们swap(to[i],to[to[i]])的过程其实是对这个循环的一次转动。 即把(a_i,a_{i+1},...a_k,a_1,...,a_{i-1})转成(a_{i+1},...a_k,a_1,...,a_{i-1},a_i)\ 那么根据循环定义，我们只要成功使其中任意a_i使得to[a_i]=a_i，则有整个循环的a_1-a_k都有to[a_j]=a_j(1\leq j \leq k)

而且对于交换x,y两行(这里指奇或偶数行的第x,y行)，首先将x移到y位置需要 y-x次翻转，再把y移到x位置需要y-x-1次，总步数为2(y-x)-1为奇数，那么必然改变另一边的奇偶性（即x为奇数时改变偶数，偶数时改变奇数）。

所以上述结论正确。

其实这是根据置换的优秀性质而设计出的方式，而非先写出方式再论证它正确。

Code

#include<bits/stdc++.h>
using namespace std;
int a[100010][3];
int to[100010],n;
int t[2];
int main(){
    scanf("%d",&n);
    for(int i=0;i<3;i++)
    for(int j=1;j<=n;j++)
    scanf("%d",&a[j][i]);
    for(int i=1;i<=n;i++){
        to[i]=a[i][1]/3+1;
        if(a[i][1]%3!=2||((a[i][0]!=a[i][1]+1||a[i][2]!=a[i][1]-1)&&(a[i][0]!=a[i][1]-1||a[i][2]!=a[i][1]+1))||i%2!=to[i]%2){
            printf("No");
            return 0;
        }
        if(a[i][0]>a[i][2]) t[i&1]^=1; 
    }
    for(int i=1;i<=n;i++)
    while(to[i]!=i){
        t[i&1^1]^=1;
        swap(to[i],to[to[i]]);
    }
    if(t[0]||t[1]) printf("No");
    else printf("Yes");
}