题解：P10454 奇数码问题

· · 题解

直接给结论

把输入的二维数组按行拉成一维数组，求出两个一维数组的逆序对数量，两个数组的逆序对数量的奇偶性相同则输出 TAK 否则输出 NIE。

为什么?

为什么直接判断奇偶性？

从移动过程来考虑。

样例

5 2 8       5 2 8
1   3         1 3
4 6 7       4 6 7

移动前数组 {5\ 2\ 8\ 1\ 3\ 4\ 6\ 7} , 移动后数组 {5\ 2\ 3\ 1\ 3\ 4\ 6\ 7} , 可观察到移动后对逆序对没有影响。

样例

5 2 8       5   8
1   3       1 2 3
4 6 7       4 6 7

移动前数组 {5\ 2\ 8\ 1\ 3\ 4\ 6\ 7} , 移动后数组 {5\ 8\ 1\ 2\ 3\ 4\ 6\ 7} , 相当于把 2，移动了 n - 1 位， 也就是将移动的数，移动了 n - 1 位。

详细来说 观察到： 移动后，所有的逆序对都变成了顺序对，所有的顺序对则变成了逆序对。

简单来说：上下移动时，空格就和离它 n - 1 位的数交换，最多变化 n - 1 个数的逆序关系，因为 n - 1 为偶数，所以逆序对的变化也是偶数，任何数加或减偶数都不会改变奇偶性。

综上，无论怎样移动都不会影响逆序对的奇偶性。

找规律发现：两个状态能够相互转换仅当两个序列的逆序对个数奇偶性相同。 为什么奇偶性相同就可行，这点证明很麻烦，这里就不说了……

代码

#include <bits/stdc++.h>
using namespace std;
int a[500005], b[500005], c[500005], n;
long long ans;
//归并求逆序对
void gb(int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    gb(l, m);
    gb(m + 1, r);
    for (int i = l, j = m + 1, k = l; i <= m || j <= r; ) { //精炼的写法大家一定学习
        if (i <= m && (a[i] <= a[j] || j > r))
            b[k++] = a[i++];
        else {
            b[k++] = a[j++];
            ans += m - i + 1;//ans 表示逆序对的个数
        }
    }
    for (int i = l; i <= r; i++)
        a[i] = b[i];
}
void gb2(int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    gb2(l, m);
    gb2(m + 1, r);
    for (int i = l, j = m + 1, k = l; i <= m || j <= r; ) {
        if (i <= m && (c[i] <= c[j] || j > r))
            b[k++] = c[i++];
        else {
            b[k++] = c[j++];
            ans += m - i + 1;
        }
    }
    for (int i = l; i <= r; i++)
        c[i] = b[i];
}
//其实可以只用一个归并，但作者较懒，就写了两个
int main() {
    int idx = 0;
    while (cin >> n) {
        idx = 0;
        ans = 0;
        for (int i = 1; i <= n * n; i++) {
            int x;
            scanf ("%d", &x);
            if (x != 0)
                a[++idx] = x;
        }
        idx = 0;
        for (int i = 1; i <= n * n; i++) {
            int x;
            scanf ("%d", &x);
            if (x != 0)
                c[++idx] = x;
        }
        gb(1, n * n - 1);//n * n - 1, 因为有1个0
        int p = ans;
        ans = 0;
        gb2(1, n * n - 1);
        int q = ans;
        if ((p & 1) == (q & 1))//奇偶性
            printf ("TAK\n");
        else
            printf ("NIE\n");
    }
    return 0;
}