OiClass PU2TI P3042 拓展的奇拼图题解

思路

首先发现这题是八数码问题的加强版，但是数据量非常大，爆搜+剪枝的方法非常的不可取，于是我们考虑是否可以通过一些神秘的判断方法来判断出是否可以构造出来。

从数据量可以感受出来应该是使用某种接近线性的算法，果断猜测是否是逆序对。把矩阵展开后去掉 \(0\)，然后计算逆序对个数，判断奇偶性即可。

代码

#include <iostream>
#include <cstring>

#define lowbit(x) (x & -x)
#define int long long
#define endl '\n'

using namespace std;

int n, a[250009], c[250009];

void add(int x) {
    for (int i = x; i <= n * n; i += lowbit(i)) {
        c[i] += 1;
    }
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

int work(int num) {
    memset(c, 0, sizeof(c));
    num *= num;
    for (int x, cnt = 1, i = 1; i <= num; i++) {
        cin >> x;
        if (x) {
            a[cnt++] = x;
        }
    }
    int res = 0;
    for (int i = 1; i < num; i++) {
        res += i - 1 - query(a[i]);
        add(a[i]);
    }
    return res;
}

signed main() {
    while (cin >> n) {
        int a = work(n), b = work(n);
        cout << ((a & 1) == (b & 1) ? "TAK\n" : "NIE\n");
    }
}