2017国家集训队作业[agc006e]Rotate 3x3

题意：

给你一个\(3*N\)的网格，每次操作选择一个\(3*3\)的网格，旋转\(180^\circ\)。问可不可以使每个位置\((i,j)\)的数为\(i+3*(j-1)\)。（\(n\leq10^5\)）

题解：

因为在操作中，一列的\(3\)个数不可能被打乱，可以预处理判断。我们思考旋转一次造成的影响有什么？记\(f(0/1)、g(0/1)\)分别是一开始奇数位\(/\)偶数位的反列和恢复到原始状态的步数模\(2\)的值。我们可以发现，假设一某个奇数位位中心，进行一次旋转，\(f(1)\)的奇偶性没有变化，而\(f(0)\)的奇偶性改变了。

又因为我们可以构造出（约定\(a\)表示正着的序列\(A\)表示反着的序列）：

\[\begin{align*}
&a& &b& &c& &d& &e&\\
&C& &B& &A& &d& &e&\\
&C& &B& &E& &D& &a&\\
&e& &b& &c& &D& &a&\\
&e& &b& &A& &d& &C&\\
&a& &B& &E& &d& &C&\\
&a& &B& &c& &D& &e&(1)\\
&a& &d& &C& &b& &e&\\
&c& &D& &A& &b& &e&\\
&c& &B& &a& &d& &e&\\
&A& &b& &C& &d& &e&(2)\\
\end{align*}
\]

构造使得我们可以将任意两个相距为二的数列交换，证明了只要移动后的网格的\(f(0)、f(1)\)奇偶性都为偶的话，存在合法方案。即有\(f(0)=g(1)、f(1)=g(0)\)时存在合法方案。步数什么的树状数组求求逆序对就可以啦。最后才想出来，我真是太弱了= =！。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define fo(i,l,r) for(int i=l;i<=r;i++)

#define of(i,l,r) for(int i=l;i>=r;i--)

using namespace std;

typedef long long ll;

inline int rd()

{

    static int x,f;

    x=0,f=1;

    char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

const int N=100010;

int n,a[4][N],v[4],f[2],g[2];

int pos[N];

inline bool cmp(int a,int b,int c){return a+1==b&&b+1==c&&c%3==0;}

inline int fabs(int a){return a<0?-a:a;}

namespace TA{

int tr[N<<2];

#define lowbit(x) (x&-x)

inline void insert(int x,int d){for(;x;x-=lowbit(x))tr[x]+=d;}

inline int query(int x){int res=0;for(;x<=n;x+=lowbit(x))res+=tr[x];return res;}

inline void clear(){fo(i,0,n)tr[i]=0;}

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    n=rd();

    fo(i,0,2)fo(j,1,n)a[i][j]=rd();

    fo(i,1,n){

        if(!cmp(a[0][i],a[1][i],a[2][i])&&!cmp(a[2][i],a[1][i],a[0][i])){puts("No");return 0;}

        int t=a[2][i]>a[0][i]?a[2][i]/3:a[0][i]/3;

        if((i-t)&1){puts("No");return 0;}pos[t]=i;

        if(a[0][i]>a[2][i])f[i%2]^=1;

    }

    int sum=0;

    for(int i=1;i<=n;i+=2){

        int now=pos[i]+(TA::query(pos[i])<<1);

        TA::insert(pos[i],1);

//      cout<<i<<' '<<now<<endl;

        if((fabs(i-now)/2)&1)g[i%2]^=1;

        sum+=fabs(i-now)/2;

    }

//  cout<<sum<<endl;

    TA::clear();sum=0;

    for(int i=2;i<=n;i+=2){

        int now=pos[i]+(TA::query(pos[i])<<1);

        TA::insert(pos[i],1);

//      cout<<i<<' '<<now<<endl;

        if((fabs(i-now)/2)&1)g[i%2]^=1;

        sum+=fabs(i-now)/2;

    }

//  cout<<sum<<endl;

//  cout<<f[0]<<' '<<f[1]<<endl;

//  cout<<g[0]<<' '<<g[1]<<endl;

    if(f[0]==g[1]&&f[1]==g[0])puts("Yes");

    else puts("No");

    return 0;

}

巴特西

2017国家集训队作业[agc006e]Rotate 3x3

2017国家集训队作业[agc006e]Rotate 3x3

题意：

题解：

最新文章

热门文章