题解：P10454 奇数码问题
题目传功门
结论
先下结论，本体的做法就是将二维数组劣化为一个一维数组，再求逆序对的个数，判断原数组的逆序对的个数是否与变化后的相同，如同则可以转化，反之不得转化。
论证
这里呢，我们可以分类讨论一下：
- 左右移动：空格与数字交换，原数组不变，逆序对个数亦不变。（如图）
原数组：1 2 3
4 5 6
7 8 -
一维：1 2 3 4 5 6 7 8
将空格向左移动后
原数组：1 2 3
4 5 6
7 - 8
一维：1 2 3 4 5 6 7 8- 上下移动：因为上下移动会使
n-1 个元素的位置发生变化，因为n-1 为偶数，所以原数组奇偶性不变。代码
#include<bits/stdc++.h>
using namespace std;
typedef int intt;
#define int long long
int n,a[505*505],b[505*505],c[505*505],sum,xb,xb2;
void qsort(int l,int r) {
if(l>=r) {
return;
}
int mid=(l+r)>>1;
qsort(l,mid);
qsort(mid+1,r);
for(int i=l,j=mid+1,k=l; i<=mid||j<=r;) {
if(i<=mid&&(a[i]<=a[j]||j>r)) {
c[k++]=a[i++];
} else {
c[k++]=a[j++];
sum+=mid-i+1;
}
}
for(int i=l; i<=r; i++)a[i]=c[i];
}
void qsort2(int l,int r) {
if(l>=r) {
return;
}
int mid=(l+r)>>1;
qsort2(l,mid);
qsort2(mid+1,r);
for(int i=l,j=mid+1,k=l; i<=mid||j<=r;) {
if(i<=mid&&(b[i]<=b[j]||j>r)) {
c[k++]=b[i++];
} else {
c[k++]=b[j++];
sum+=mid-i+1;
}
}
for(int i=l; i<=r; i++)b[i]=c[i];
}
signed main() {
while(cin>>n) {
xb = 0;
xb2 = 0;
int x;
for(int i=1; i<=n*n; i++) {
cin>>x;
if(x!=0) {
a[++xb]=x;
}
}
for(int i=1; i<=n*n; i++) {
cin>>x;
if(x!=0) {
b[++xb2]=x;
}
}
sum=0;
qsort(1,n*n-1);
int cnt1=sum;
sum=0;
qsort2(1,n*n-1);
int cnt2=sum;
if((cnt1&1)==(cnt2&1))cout<<"TAK"<<endl;
else cout<<"NIE"<<endl;
}
return 0;
}