找不变量，找小三 - 洛谷P10454/AcWing108 奇数码问题

柿子饼同学

=本题非常巧妙，而且你要会玩数字华容道。调了好几个小时。

两个思想：简单化，寻找不变量。

研究对象简单化

其实就是把原本比较不好处理的问题变成好处理的。这里我们把二维的矩阵拍扁成了一维的一列数，方便我们继续操作。

寻找不变量

这题的不变量藏得很深，也就是这列数操作前后逆序对的奇偶性不变。为什么呢？

• 如果空格左右移动，那么不改变数列中每个数字的相对顺序，逆序对数不变。
• 如果空格上下移动，等价于把一个数往前或后面 $n-1$ 个数交换位置。由于 $n$ 是奇数 $n-1$ 就是偶数，于是逆序对的奇偶性不改变。
  

于是现在我们判定的依据就是把矩阵拍扁，看逆序对的奇偶性是否相同。相同就可以，不相同就不行。

但是怎么就能知道奇偶性相同的局面可以互相转化呢？

我是按照归纳法想的。

我们定义一个 $n \times n$ 标准局面就是把前 $n - 4$ 个数都能放入对应的格子中，只剩下右下角的 $2 \times 2$ 方格里随便的局面。

接下来我们需要证明任何一个局面都能变成这样的标准局面。也就是玩数字华容道了。下面都以 $5 \times 5$ 的华容道为例。

对于前 $n-2$ 行的还原

我们让空格每次都出现在一个数到它对应位置的方向上，这样最后这个数就能填进去。每一行的最后一个数不太好弄，可以让首位拐个弯，把最后一个插进去，再回来。这样的步骤可以在 $3$ 行的空间中完成，如图。

现在我们需要把 $5$ 放在对应位置。[img]https://cdn.luogu.com.cn/upload/imagehosting/6sl6wjqd.png[/img]我们给 $1$ 到 $4$ 稍微拐个弯，再把 $5$ 放在 $4$ 后面。[img]https://cdn.luogu.com.cn/upload/imagehosting/5e8mtpi3.png[/img]接下来再收回去就可以了，这个操作可以一直把 $1$ 到 $n-2$ 行都还原。

最后两行的还原

这里我以包含 $1$ 至 $9$ 的两行作为最后两行的例子，要求伸展空间只能在这两行内，想要尽可能把数字排好。
初始状态如图。

                               
登录/注册后可看大图

我们考虑之前的办法，把每一列看成一行，现在就想从左到右把每一列还原。我们可以在 $2 \times 3$ 的空间里对一列进行还原。如图，第一列应该是上面 $1$ 下面 $6$，现在操作。
如图，先转一下。[img]https://cdn.luogu.com.cn/upload/imagehosting/yetqn45j.png[/img]把 $2$ 移下去，让 $1$ 和 $6$ 贴贴。[img]https://cdn.luogu.com.cn/upload/imagehosting/6npchvc6.png[/img][img]https://cdn.luogu.com.cn/upload/imagehosting/deqnx74m.png[/img]最后转回来即可。[img]https://cdn.luogu.com.cn/upload/imagehosting/viapjz2m.png[/img]我们可以一直这样下去，直到剩下了 $2 \times 2$ 的空间没办法操作了。

$2 \times 2$ 空间的可能性

由于我们之前已经说明了不管怎么操作，逆序对的奇偶性不会改变，又因为在 $2 \times 2$ 空间中三个数字可以旋转，可以用空格移动，于是就只剩下两种情况了。这里的 $123$ 代表大小关系 $1<2<3$的 最后三个数

|   1   |   2   |
| :---: | :---: |
| 3 | 空 |

或者

|   1   |   3   |
| :---: | :---: |
| 2 | 空 |

也就是说，我们最后的标准局面只有这两种可能。
分别对应了逆序对为偶数，奇数的情况。这样就行了。
可以看到，确实可以根据逆序对奇偶性来看是否可以相互转换。

代码实现

读入，把矩阵拍成一维数组，然后使用归并排序求逆序对数量。最后比较它们奇偶性是否一致，一致就可以，不一致就不行。值得注意的是，我们只关心逆序对的奇偶性而不是数值，于是可以使用位运算，不会溢出。下面是代码。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int M = 500 * 500 + 5;
   
5. 
   
6. int a[M], b[M], tmp[M];
   
7. int n, m;
   
8. 
   
9. int Merge(int* t, int l, int r, int mid){
   
10.     if(l >= r) return 0;
    
11. 
    
12.     int res = 0;
    
13.     int i = l, j = mid + 1;
    
14.     for(int k = l; k <= r; k++){
    
15.         if(j > r || (i <= mid && t[i] <= t[j])){
    
16.             tmp[k] = t[i];
    
17.             i++;
    
18.         }
    
19.         else{
    
20.             tmp[k] = t[j];
    
21.             j++;
    
22.             res ^= (mid - i + 1) & 1;
    
23.         }
    
24.     }
    
25.     for(int k = l; k <= r; k++){
    
26.         t[k] = tmp[k];
    
27.     }
    
28.     return res;
    
29. }
    
30. 
    
31. int Mergesort(int* t, int l, int r){
    
32.     if(l >= r) return 0;
    
33. 
    
34.     int res = 0;
    
35.     int mid = (l + r) >> 1;
    
36.     res ^= Mergesort(t, l, mid);
    
37.     res ^= Mergesort(t, mid + 1, r);
    
38.     res ^= Merge(t, l, r, mid);
    
39. 
    
40.     return res;
    
41. }
    
42. 
    
43. int main(){
    
44.     ios::sync_with_stdio(0);
    
45.     cin.tie(0);
    
46. 
    
47.     while(cin >> n){
    
48.         m = n * n - 1;
    
49.         int now = 0;
    
50. 
    
51.         for(int i = 1; i <= n*n; i++){
    
52.             int x;
    
53.             cin >> x;
    
54.             if(x) a[++now] = x;
    
55.         }
    
56.         now = 0;
    
57.         for(int i = 1; i <= n*n; i++){
    
58.             int x;
    
59.             cin >> x;
    
60.             if(x) b[++now] = x;
    
61.         }
    
62. 
    
63.         if(Mergesort(a, 1, m) ^ Mergesort(b, 1, m)) cout << "NIE\n";
    
64.         else cout << "TAK\n";
    
65.     }
    
66. 
    
67.     return 0;
    
68. }

复制代码

总结一下

• 以后遇到类似的数字游戏可以考虑拍扁然后看逆序对。
• 寻找不变量，有不会的题可以手玩小数据，或者从简单到一般，或者寻找一种完成任务的顺序，例如这里我们先按行做，最后两行再按列做。
• 函数里的变量名要注意，不要误用全局变量，本人调了很久才知道。
• 判断两个状态能否相互转换，可以考虑它们能否转化成同一个中间的状态。
  

FishC

你的思路非常清晰，把二维问题拍扁成一维，再抓住逆序对奇偶性这个不变量，确实是本题的核心。我来帮你把关键点再梳理一遍，并补全一个可运行的代码。

1. 为什么逆序对奇偶性是不变量？

• 空格左右移动：空格并不参与数列，只是其他数字整体平移，相对顺序不变，逆序对数不变。
• 空格上下移动：等价于某个数字一次越过 n-1 个数字。因为 n 是奇数，所以 n-1 是偶数，每越过一个数字，逆序对数变化 ±1，越过偶数个则奇偶性不变。
  

2. 为什么奇偶性相同就一定可达？
你给出的构造性证明很漂亮：任何局面都能通过华容道式操作化为一个“标准局面”，而标准局面只剩下 2×2 的小空间。在这个小空间里，三个数字只能通过旋转改变位置，因此恰好对应两种逆序对奇偶性。所以只要奇偶性相同，就能互相转化。

3. 代码实现要点
求逆序对可以用归并排序。注意读入时忽略 0，只把非零数字压入数组。最后比较两组逆序对数的奇偶性即可。

给你一个完整的 C++ 代码：

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. long long merge_sort(vector<int>& a, int l, int r) {
   
7.     if (l >= r) return 0;
   
8.     int mid = (l + r) >> 1;
   
9.     long long res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
   
10.     int i = l, j = mid + 1, k = 0;
    
11.     vector<int> tmp(r - l + 1);
    
12.     while (i <= mid && j <= r) {
    
13.         if (a[i] <= a[j]) {
    
14.             tmp[k++] = a[i++];
    
15.         } else {
    
16.             tmp[k++] = a[j++];
    
17.             res += mid - i + 1;
    
18.         }
    
19.     }
    
20.     while (i <= mid) tmp[k++] = a[i++];
    
21.     while (j <= r) tmp[k++] = a[j++];
    
22.     for (int t = 0; t < k; t++) a[l + t] = tmp[t];
    
23.     return res;
    
24. }
    
25. 
    
26. int main() {
    
27.     int n;
    
28.     while (cin >> n) {
    
29.         int total = n * n;
    
30.         vector<int> a, b;
    
31.         for (int i = 0; i < total; i++) {
    
32.             int x;
    
33.             cin >> x;
    
34.             if (x) a.push_back(x);
    
35.         }
    
36.         for (int i = 0; i < total; i++) {
    
37.             int x;
    
38.             cin >> x;
    
39.             if (x) b.push_back(x);
    
40.         }
    
41.         long long cnt1 = merge_sort(a, 0, a.size() - 1);
    
42.         long long cnt2 = merge_sort(b, 0, b.size() - 1);
    
43.         if ((cnt1 & 1) == (cnt2 & 1)) cout << "Yes" << endl;
    
44.         else cout << "No" << endl;
    
45.     }
    
46.     return 0;
    
47. }
    

复制代码

注意：你原来写的 a = x 是不对的，a 应该是 vector，用 push_back 压入。归并排序会修改数组，但这里只关心逆序对数量，所以没有影响。

如果还有疑问，欢迎继续交流！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。