12
6
2017
0

BZOJ4354

被MYC吊打

首先,似乎很难考虑单独的操作,所以考虑,一些操作叠加起来能达到什么效果?

假设当前是这个样子,我要交换3和9。

        0

2 3 4 5 6

        7

        8

        9

那么我可以先把第4列上移3次,然后第2行后移2次,然后第4列下移3次,然后第2行左移2次。

这样就得到了

        0

2 5 4 9 6

        7

        8

        3

我们发现这样只有3个数被移动了,也就是说,可以借助一个拐角处的数改变这3个数的位置。

之后就比较容易证明,任何三个数都可以互相换位置,也就是说假设有三个位置依次a b c,一定可以换成b c a或c a b

现在问题就显然容易了许多。

考虑这样一个做法,如果不同的数数量不一样显然No。

否则考虑依次贪心下来,让每个位置上的数变成应该变成的数。

这样操作之后,要么已经完全操作好了,要么还剩恰好2个位置上的数正好位置不对(显然)。

容易把这两个数挪动到同行,然后挪动到这行的最后两个。

考虑能否弄好,

如果n是偶数,

比方说目标是abcdef,当前是abcdfe。

移动一位之后再三个三个换换就好了。

如果是奇数是不行的。

为什么?可以从逆序对奇偶性来考虑。

大概就是这样了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef pair<int,int> pa;
typedef long double ld;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int x,X,Y,y,S[100010],T,n,a[111][111],b[1111][111];
bool ok,flag;
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        memset(S,0,sizeof(S));
        FOR(i,1,n)
            FOR(j,1,n)
                getint(a[i][j]),S[a[i][j]]++;
        FOR(i,1,n)
            FOR(j,1,n)
                getint(b[i][j]),S[b[i][j]]--;
        ok=1;
        FOR(i,1,10000)
            if (S[i]!=0) ok=0;
        if (!ok){puts("No");continue;}
        FOR(i,1,n)
            FOR(j,1,n)
                if (a[i][j]!=b[i][j]){
                    x=y=X=Y=0;
                    FOR(k,1,n)
                        FOR(l,1,n)
                            if (k>i || k==i && l>j){
                                if (a[k][l]==b[i][j] && x==0) x=k,y=l;
                                else X=k,Y=l;
                            }
                    if (x==0 || X==0){ok=0;break;}
                    int t=a[i][j];
                    a[i][j]=a[x][y];
                    a[x][y]=a[X][Y];
                    a[X][Y]=t;
                }
        flag=0;
        FOR(i,1,n)
            FOR(j,1,n){
                S[a[i][j]]++;
                if (S[a[i][j]]>1) flag=1;
            }
        if (n%2==0) flag=1;
        if (flag){puts("Yes");continue;}
        ok=1;
        FOR(i,1,n)
            FOR(j,1,n)
                if (a[i][j]!=b[i][j]) ok=0;
        puts(ok?"Yes":"No");
    }
    return 0;
}
Category: BZOJ | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com