题解：AT_agc006_e [AGC006E] Rotate 3x3

· · 题解

Solution

这题真的有黑吗？

考虑先找一找必要条件。显然，我们把每一列当做整体，那么每一列的属性有位置 p 和方向 d。

显然每次操作列的位置的奇偶性不变，即必须满足 p_i \equiv i \pmod 2。

然后模拟对奇偶位置的排序，得到一个顺序合适但是方向还不满足的组合。

显然上述的排序是必不可少的，和逆序对数相关，可以直接计算。

注意到后续的调整操作，奇数位和偶数位执行的次数都必须是偶数次，否则最后会乱序：那么我们认为操作对中心列的朝向没有影响。

那么发现每次操作，对于旁边列的方向之和的奇偶性不变（朝上是 0，朝下是 1），那么必要条件呼之欲出：

奇数位置的 d 之和的奇偶性与其 p 的逆序对数的奇偶性相同，偶数位置 d 之和的奇偶性也和其 p 的逆序对数的奇偶性相同。

由于 n \ge 5，所以给出一组保持位置不变且修改 p 和 p+2 的 d 的构造。根据这个构造，就可以随手修改使得 d 调整完毕。

ABCDE \to \overline C \overline B \overline A DE \to \overline C \overline B \overline E \overline D A \to EBC \overline D A \to EB \overline A D \overline C \to A \overline B \overline E D \overline C \to A \overline B C \overline D E

UPD：好像还要证明第一列和最后一列的情况，补充第一列即可。

ABCDE \to A \overline D \overline C \overline B E \to C D \overline A \overline B E \to C B A \overline D E \to C \overline B A D E \to \overline A B \overline C DE

中间一步用到了上面那种方法的结论。

复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,a[4][MAXN],flp[MAXN],pos[MAXN],pre[MAXN],tr[MAXN];
void update(int pos) {
    while(pos<=n) tr[pos]^=1,pos+=pos&-pos;
    return ;    
}
int query(int pos) {
    int ans=0;
    while(pos) ans^=tr[pos],pos-=pos&-pos;
    return ans; 
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,3) ffor(j,1,n) cin>>a[i][j];
    ffor(i,1,n) {
        if(a[2][i]==a[1][i]+1&&a[3][i]==a[2][i]+1) {
            if((a[1][i]+2)%3) return cout<<"No",0;
            pos[(a[1][i]+2)/3]=i;   
        }
        else if(a[2][i]==a[3][i]+1&&a[1][i]==a[2][i]+1) {
            if((a[3][i]+2)%3) return cout<<"No",0;
            pos[(a[3][i]+2)/3]=i,flp[(a[3][i]+2)/3]=1;
        }
        else return cout<<"No",0;
    }
    ffor(i,1,n) if((pos[i]-i)%2) return cout<<"No",0;
    int sum[2]={0,0},psl[2]={0,0};
    ffor(i,1,n) sum[i&1]^=flp[i];
    ffor(i,1,n) if(i%2==1) psl[0]^=query(n)^query(pos[i]),update(pos[i]);
    ffor(i,1,n) tr[i]=0;    
    ffor(i,1,n) if(i%2==0) psl[1]^=query(n)^query(pos[i]),update(pos[i]);
    if(sum[0]!=psl[0]||sum[1]!=psl[1]) return cout<<"No",0;
    cout<<"Yes";
    return 0;
}