我要评论题面：奇数码问题
思路：
找了好久，没有找到奇数码问题和 数码问题的详细证明。先记个结论。
奇数码游戏两个局面可达，当且仅当两个局面下网络中的数依次写成不含零的 到 的序列后，逆序对个数的奇偶性相同。
结论必要性证明：空格（即 )左右移动的时候，我们列出出来的序列是不变的；空格上（下）移动时，相当于某个数与它后（前）边 个数交换了位置，因为 是偶数，所以逆序对数的变化也是一个偶数。
拓展到 为偶数的情况，此时两个局面可达，当且仅当两个局面对应的网络写成序列之后，逆序对数之差和两个局面下空格所在的行数之差奇偶性相同。
数码问题也是根据上面两个结论来进行判定有解性的。具体的，慢慢找。
代码：
#include <bits/stdc++.h>
#define sc scanf
#define pf printf
using namespace std;
const int N = 250010;
int a[N], b[N], w[N];
//归并排序求逆序对数
int merge(int l, int r, int x[])
{
if(l == r) return 0;
int mid = l + r >> 1;
int res = merge(l, mid, x) + merge(mid + 1, r, x);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r) {
if(x[i] <= x[j]) w[k++] = x[i++];
else {
res += mid - i + 1;
w[k++] = x[j++];
}
}
while(i <= mid) w[k++] = x[i++];
while(j <= r) w[k++] = x[j++];
for(i = l, j = 0; i <= r; i++, j++) x[i] = w[j];
return res;
}
void read(int *x, int len)
{
int k = 0;
for(int i = 0; i < len; i++) {
int num; sc("%d", &num);
if(num != 0) x[k++] = num;
}
}
int main()
{
int n;
while(cin >> n) {
read(a, n * n);
read(b, n * n);
int cnt_a = merge(0, n * n - 1, a);
int cnt_b = merge(0, n * n - 1, b);
//要使得两个局面可达
//当且仅当两个局面的不含空格的序列的逆序对个数的奇偶性一致
if((cnt_a & 1) == (cnt_b & 1)) puts("TAK");
else puts("NIE");
}
}
本文地址：https://blog.csdn.net/qq_45371462/article/details/107876269
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论