题意分析

题目要求判断三维滑块拼图是否可解。关键点包括：

1. 立方体尺寸为$M \times M \times M$，包含$M^3-1$个编号滑块和$1$个空格
2. 每次只能将相邻滑块移入空格
3. 原始配置为$(x,y,z)$位置存放$z·M^2+y·M+x+1$号滑块，$(M-1,M-1,M-1)$为空
4. 需要判断任意打乱状态能否通过合法移动恢复原始排列

解题思路

基于二维十五拼图的推广理论：

1. 逆序数判定：计算所有滑块排列的逆序数
2. 空格位置影响：
   • 当$M$为奇数时，逆序数必须为偶数
   • 当$M$为偶数时，需额外考虑空格所在层数的奇偶性
3. 树状数组优化：高效计算逆序数

实现步骤

1. 输入处理：
   • 读取测试用例数$T$
   • 对每个用例读取立方体尺寸$M$
2. 逆序数计算：
   • 使用树状数组动态维护数字出现情况
   • 统计每个数字后方比它小的数字个数
3. 空格位置修正：
   • 当$M$为偶数时，根据空格所在行列调整逆序数奇偶性
4. 结果判定：
   • 检查最终逆序数是否符合可解条件

C++实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 1000005;
int sum[maxn];

inline int lowbit(int x) { return x & -x; }

void add(int p, int x) {
    while (p < maxn) {
        sum[p] += x;
        p += lowbit(p);
    }
}

int query(int p) {
    int ret = 0;
    while (p > 0) {
        ret += sum[p];
        p -= lowbit(p);
    }
    return ret;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int M;
        scanf("%d", &M);
        memset(sum, 0, sizeof(sum));
        
        int rev = 0, zero_pos = 0;
        for (int i = 0; i < M*M*M; ++i) {
            int d;
            scanf("%d", &d);
            if (d == 0) {
                zero_pos = i;
            } else {
                rev += query(M*M*M) - query(d);
                add(d, 1);
                rev %= 2;
            }
        }

        if (M % 2 == 0) {
            int z = zero_pos / (M * M);
            int y = (zero_pos % (M * M)) / M;
            if (((M-1-z) + (M-1-y)) % 2 == 1) {
                rev ^= 1;
            }
        }

        puts(rev == 0 ? "Puzzle can be solved." : "Puzzle is unsolvable.");
    }
    return 0;
}

代码说明

1. 核心数据结构：

   • 树状数组sum用于高效计算逆序数
   • lowbit运算实现快速索引

2. 关键函数：

   • add()：更新树状数组
   • query()：查询前缀和

3. 算法流程：

   • 遍历所有滑块，计算逆序数（$O(M^3 \log M)$）
   • 对偶数阶立方体，调整空格位置的影响
   • 根据逆序数奇偶性判定可解性

4. 复杂度分析：

   • 时间复杂度：$O(M^3 \log M)$
   • 空间复杂度：$O(M^3)$

5. 示例分析：

   • 输入$M=2$时：
     • 第一测试用例逆序数为$1$（不可解）
     • 第二测试用例逆序数为$0$（可解）