题目传功门

结论

先下结论，本体的做法就是将二维数组劣化为一个一维数组，再求逆序对的个数，判断原数组的逆序对的个数是否与变化后的相同，如同则可以转化，反之不得转化。

论证

这里呢，我们可以分类讨论一下：

左右移动：空格与数字交换，原数组不变，逆序对个数亦不变。（如图）

CPP

原数组：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$ 为偶数，所以原数组奇偶性不变。

代码

CPP

#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;
}

题解：P10454 奇数码问题

文章操作

题目传功门

结论

论证

代码

相关推荐

评论

题解：P10454 奇数码问题