奇数码---结论题（逆序对）

通过诸多伟大的数学家证明，如果要判断奇数码是否能从一个状态走到另一个状态，只需要判断两个状态的逆序对的 奇偶性是否一样即可

即从左到右从上到下的顺序搞成一维（0直接删掉），然后判断二者逆序对的奇偶性是否一致，结束。

#include <bits/stdc++.h> using namespace std; const int MA = 3e5+10; int b[MA],a[MA],c[MA];//ab存两个状态，c逆序对辅助数组 void merge(int a[],int l,int r,long long &cnt){//求逆序对 if(l >= r) return; int mid = (l+r)>>1; merge(a,l,mid,cnt); merge(a,mid+1,r,cnt); int i = l,j = mid+1; for (int k = l; k <= r; k++){ if(j > r || i <= mid && a[i]<a[j]) c[k] = a[i++]; else { c[k] = a[j++]; cnt += mid - i + 1; } } for (int k = l; k <= r; k++) a[k] = c[k]; return ; } int main() { int n,k,j; while(~scanf("%d",&n)){ j = 0; for (int i = 0; i < n*n; i++){ scanf("%d",&k); if(k != 0) a[j++] = k; } j = 0; for (int i = 0; i < n*n; i++){ scanf("%d",&k); if(k != 0) b[j++] = k; } long long b1 = 0,b2 = 0; merge(a,0,n*n-1,b1); merge(b,0,n*n-1,b2); b1 &= 1; b2 &= 1; //奇偶判断 if(b1 == b2) printf("TAK\n"); else printf("NIE\n"); } return 0; }