UVA 716 Commedia dell'arte：三維八數碼置換奇偶性判斷可解性

問題描述

n×n×n 立方體（n 奇/偶），數字 0~n³-1，0 為空位。判斷能否通過移動 0 恢復有序狀態。

置換奇偶性判斷

• 將三維坐標 (x,y,z) 映射為一維索引 idx = z*n² + x*n + y。
• 去除 0 後得到長度 N=n³-1 的排列。
• 計算逆序對數 inv。
• n 奇數：可解 ⇔ inv 為偶數。
• n 偶數：需考慮 0 的行號（從底向上）。可解 ⇔ (inv + row0) % 2 == 0。
  代碼中通過將 0 移動到 (n-1,n-1,n-1) 位置（每次交換改變逆序對奇偶性），轉化為奇數情況判斷。

核心代碼邏輯

ll merge_sort(int l, int r, int *a, int *b) { // 歸併排序計算逆序對
    if (l==r) return 0;
    int m=(l+r)/2;
    ll ret = merge_sort(l,m,a,b) + merge_sort(m+1,r,a,b);
    int p=l, q=m+1, mv=l;
    while (p<=m || q<=r) {
        if (q>r || (p<=m && a[p]

總結
三維八數碼推廣：置換奇偶性不變量決定可解性。奇數階只看逆序對；偶數階需結合空位行號。代碼通過模擬移動空位到終點，統一轉化為奇數階判斷，極其巧妙。歸併排序 O(N log N) 計算逆序對，N ≤ 10⁶ 完全足夠。