题解 AT2166 【[AGC006E] Rotate 3x3】

· · 题解

提供一个思路小有不同的做法。

首先肯定是直接判掉每一列不合法的情况，然后把每一列看成一个数，但有正负之分。

然后我们发现一次操作是形如: swap(x_{i},x_{x+2}) 的，所以每一次操作是不会改变这一列的奇偶性的

By the way，有一道类似的题思想也是这个，算是这道题的简化版，大家可以做一下，还是很妙（[AGC003C] BBuBBBlesort!）。

接着刚才的思路，既然操作不会改变奇偶性，我们可以分奇数和偶数列来考虑，下面只考虑奇数列。

对于奇数列考虑怎样换到它，显然是用奇数列的1,2,3,...(即原序列1,3,5...)通过一些交换得到，最小的交换次数就是逆序对数。

但是我们还需满足正负的要求，注意到若只交换奇数列，每个数的正负是已经确定的了，交换一次就乘 -1 ，但我们还可以交换偶数列，通过偶数列来改变正负。

而偶数列的有效交换次数也是确定的，所以可以判断奇偶性来判断是否可行。

具体我们可以看看代码实现，我的这份代码是 O(nlogn) 的，因为要求逆序对数，其他大佬诸如 @Fee_clе6418，都可以直接换，据他说复杂度为 O(n),orz,orz,orz。

上代码：

#include<bits/stdc++.h>
#define N 100005
#define lowbit(x) x&-x
using namespace std;
int c[2][N],cnt[2];
int n,f[4][N],wz[2][N];
long long sx[2],ans[2];
const int inf=0x3f3f3f3f,mod=998244353;
inline int read() {
    int s=0,f=0;
    char ch=getchar();
    while(ch<48||ch>57)f=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58)s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return f?-s:s;
}
void Get(int x,int bj) {
    if((f[1][x]+2)/3!=(f[2][x]+2)/3)puts("No"),exit(0);
    if((f[1][x]+2)/3!=(f[3][x]+2)/3)puts("No"),exit(0);
    if((f[2][x]+2)/3!=(f[3][x]+2)/3)puts("No"),exit(0);
    if(f[1][x]<f[2][x]&&f[2][x]<f[3][x]) {
        if((((f[1][x]+2)/3)&1)!=bj)puts("No"),exit(0);
        wz[bj][++cnt[bj]]=(f[1][x]+5)/6;
        return;
    }
    if(f[1][x]>f[2][x]&&f[2][x]>f[3][x]) {
        if((((f[1][x]+2)/3)&1)!=bj)puts("No"),exit(0);
        wz[bj][++cnt[bj]]=(f[1][x]+5)/6,++sx[bj];
        return;
    }
    puts("No"),exit(0);
}
int Ask(int opt,int x) {
    int ans=0;
    for(; x; x-=lowbit(x))ans+=c[opt][x];
    return ans;
}
void Add(int opt,int x) {
    for(; x<=n; x+=lowbit(x))++c[opt][x];
}
int main() {
    n=read();
    for(int i=1; i<=3; ++i)for(int j=1; j<=n; ++j)f[i][j]=read();
    for(int j=1; j<=n; ++j)Get(j,j&1);
    for(int i=cnt[0]; i; --i)ans[0]+=Ask(0,wz[0][i]),Add(0,wz[0][i]);
    for(int i=cnt[1]; i; --i)ans[1]+=Ask(1,wz[1][i]),Add(1,wz[1][i]);
    if((ans[0]&1)^(sx[1]&1))return puts("No"),0;//ans是逆序对数，sx是奇数列和偶数列需要由正到负的次数
    if((ans[1]&1)^(sx[0]&1))return puts("No"),0;
    puts("Yes");
    return 0;
}

如果我的题解给你带来了帮助，点一个赞吧。

如果有问题，可以发到讨论，我私信告诉您。