找不变量，找小三 - 洛谷P10454/AcWing108 奇数码问题
本帖最后由 柿子饼同学 于 2026-8-28 14:43 编辑=本题非常巧妙，而且你要会玩数字华容道。调了好几个小时。
两个思想：简单化，寻找不变量。
研究对象简单化
其实就是把原本比较不好处理的问题变成好处理的。这里我们把二维的矩阵拍扁成了一维的一列数，方便我们继续操作。
寻找不变量
这题的不变量藏得很深，也就是这列数操作前后逆序对的奇偶性不变。为什么呢？
[*]如果空格左右移动，那么不改变数列中每个数字的相对顺序，逆序对数不变。
[*]如果空格上下移动，等价于把一个数往前或后面 $n-1$ 个数交换位置。由于 $n$ 是奇数 $n-1$ 就是偶数，于是逆序对的奇偶性不改变。
于是现在我们判定的依据就是把矩阵拍扁，看逆序对的奇偶性是否相同。相同就可以，不相同就不行。
但是怎么就能知道奇偶性相同的局面可以互相转化呢？
我是按照归纳法想的。
我们定义一个 $n \times n$ 标准局面就是把前 $n - 4$ 个数都能放入对应的格子中，只剩下右下角的 $2 \times 2$ 方格里随便的局面。
接下来我们需要证明任何一个局面都能变成这样的标准局面。也就是玩数字华容道了。下面都以 $5 \times 5$ 的华容道为例。
对于前 $n-2$ 行的还原
我们让空格每次都出现在一个数到它对应位置的方向上，这样最后这个数就能填进去。每一行的最后一个数不太好弄，可以让首位拐个弯，把最后一个插进去，再回来。这样的步骤可以在 $3$ 行的空间中完成，如图。
现在我们需要把 $5$ 放在对应位置。https://cdn.luogu.com.cn/upload/imagehosting/6sl6wjqd.png我们给 $1$ 到 $4$ 稍微拐个弯，再把 $5$ 放在 $4$ 后面。https://cdn.luogu.com.cn/upload/imagehosting/5e8mtpi3.png接下来再收回去就可以了，这个操作可以一直把 $1$ 到 $n-2$ 行都还原。
最后两行的还原
这里我以包含 $1$ 至 $9$ 的两行作为最后两行的例子，要求伸展空间只能在这两行内，想要尽可能把数字排好。
初始状态如图。https://cdn.luogu.com.cn/upload/image_hosting/7q04vm0e.png我们考虑之前的办法，把每一列看成一行，现在就想从左到右把每一列还原。我们可以在 $2 \times 3$ 的空间里对一列进行还原。如图，第一列应该是上面 $1$ 下面 $6$，现在操作。
如图，先转一下。https://cdn.luogu.com.cn/upload/imagehosting/yetqn45j.png把 $2$ 移下去，让 $1$ 和 $6$ 贴贴。https://cdn.luogu.com.cn/upload/imagehosting/6npchvc6.pnghttps://cdn.luogu.com.cn/upload/imagehosting/deqnx74m.png最后转回来即可。https://cdn.luogu.com.cn/upload/imagehosting/viapjz2m.png我们可以一直这样下去，直到剩下了 $2 \times 2$ 的空间没办法操作了。
$2 \times 2$ 空间的可能性
由于我们之前已经说明了不管怎么操作，逆序对的奇偶性不会改变，又因为在 $2 \times 2$ 空间中三个数字可以旋转，可以用空格移动，于是就只剩下两种情况了。这里的 $123$ 代表大小关系 $1<2<3$的 最后三个数
| 1 | 2 |
| :---: | :---: |
| 3 | 空 |
或者
| 1 | 3 |
| :---: | :---: |
| 2 | 空 |
也就是说，我们最后的标准局面只有这两种可能。
分别对应了逆序对为偶数，奇数的情况。这样就行了。
可以看到，确实可以根据逆序对奇偶性来看是否可以相互转换。
代码实现
读入，把矩阵拍成一维数组，然后使用归并排序求逆序对数量。最后比较它们奇偶性是否一致，一致就可以，不一致就不行。值得注意的是，我们只关心逆序对的奇偶性而不是数值，于是可以使用位运算，不会溢出。下面是代码。
#include <bits/stdc++.h>
using namespace std;
const int M = 500 * 500 + 5;
int a, b, tmp;
int n, m;
int Merge(int* t, int l, int r, int mid){
if(l >= r) return 0;
int res = 0;
int i = l, j = mid + 1;
for(int k = l; k <= r; k++){
if(j > r || (i <= mid && t <= t)){
tmp = t;
i++;
}
else{
tmp = t;
j++;
res ^= (mid - i + 1) & 1;
}
}
for(int k = l; k <= r; k++){
t = tmp;
}
return res;
}
int Mergesort(int* t, int l, int r){
if(l >= r) return 0;
int res = 0;
int mid = (l + r) >> 1;
res ^= Mergesort(t, l, mid);
res ^= Mergesort(t, mid + 1, r);
res ^= Merge(t, l, r, mid);
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while(cin >> n){
m = n * n - 1;
int now = 0;
for(int i = 1; i <= n*n; i++){
int x;
cin >> x;
if(x) a[++now] = x;
}
now = 0;
for(int i = 1; i <= n*n; i++){
int x;
cin >> x;
if(x) b[++now] = x;
}
if(Mergesort(a, 1, m) ^ Mergesort(b, 1, m)) cout << "NIE\n";
else cout << "TAK\n";
}
return 0;
}
总结一下
[*]以后遇到类似的数字游戏可以考虑拍扁然后看逆序对。
[*]寻找不变量，有不会的题可以手玩小数据，或者从简单到一般，或者寻找一种完成任务的顺序，例如这里我们先按行做，最后两行再按列做。
[*]函数里的变量名要注意，不要误用全局变量，本人调了很久才知道。
[*]判断两个状态能否相互转换，可以考虑它们能否转化成同一个中间的状态。
你的思路非常清晰，把二维问题拍扁成一维，再抓住逆序对奇偶性这个不变量，确实是本题的核心。我来帮你把关键点再梳理一遍，并补全一个可运行的代码。
1. 为什么逆序对奇偶性是不变量？
[*]空格左右移动：空格并不参与数列，只是其他数字整体平移，相对顺序不变，逆序对数不变。
[*]空格上下移动：等价于某个数字一次越过 n-1 个数字。因为 n 是奇数，所以 n-1 是偶数，每越过一个数字，逆序对数变化 ±1，越过偶数个则奇偶性不变。
2. 为什么奇偶性相同就一定可达？
你给出的构造性证明很漂亮：任何局面都能通过华容道式操作化为一个“标准局面”，而标准局面只剩下 2×2 的小空间。在这个小空间里，三个数字只能通过旋转改变位置，因此恰好对应两种逆序对奇偶性。所以只要奇偶性相同，就能互相转化。
3. 代码实现要点
求逆序对可以用归并排序。注意读入时忽略 0，只把非零数字压入数组。最后比较两组逆序对数的奇偶性即可。
给你一个完整的 C++ 代码：
#include <iostream>
#include <vector>
using namespace std;
long long merge_sort(vector<int>& a, int l, int r) {
if (l >= r) return 0;
int mid = (l + r) >> 1;
long long res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
int i = l, j = mid + 1, k = 0;
vector<int> tmp(r - l + 1);
while (i <= mid && j <= r) {
if (a <= a) {
tmp = a;
} else {
tmp = a;
res += mid - i + 1;
}
}
while (i <= mid) tmp = a;
while (j <= r) tmp = a;
for (int t = 0; t < k; t++) a = tmp;
return res;
}
int main() {
int n;
while (cin >> n) {
int total = n * n;
vector<int> a, b;
for (int i = 0; i < total; i++) {
int x;
cin >> x;
if (x) a.push_back(x);
}
for (int i = 0; i < total; i++) {
int x;
cin >> x;
if (x) b.push_back(x);
}
long long cnt1 = merge_sort(a, 0, a.size() - 1);
long long cnt2 = merge_sort(b, 0, b.size() - 1);
if ((cnt1 & 1) == (cnt2 & 1)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
注意：你原来写的 a = x 是不对的，a 应该是 vector，用 push_back 压入。归并排序会修改数组，但这里只关心逆序对数量，所以没有影响。
如果还有疑问，欢迎继续交流！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]