1. 题目背景与核心思路解析
P15652 [省选联考 2026] 排列游戏是一道考察排列构造与mex函数性质的交互题。题目要求我们通过不超过n次的mex查询，构造出一个长度为n的排列，使其满足特定的mex条件。
核心思路在于利用mex函数的单调性质：
- 前缀mex数组s具有非递减特性
- 当s[i] ≠ s[i+1]时，可以确定a[i+1] = s[i]
- 对于未被直接确定的数字，需要利用mex函数的区间性质确定其可能位置范围
2. 关键算法实现细节
2.1 特殊情况的处理
当0位于排列首位时，解法最为直观：
- 计算前缀mex数组s
- 对于每个i，若s[i] ≠ s[i+1]，则a[i+1] = s[i]
- 剩余数字填入任意满足s数组的位置
// 示例代码片段 for(int i=0; i<n; i++) { int u = query(0, i); if(u != prev_mex) { a[i] = prev_mex; filled[prev_mex] = true; } prev_mex = u; }2.2 一般情况的扩展处理
当0不在首位时，需要结合前后缀mex信息：
- 首先定位0的位置k
- 对[0,k-1]区间处理后缀mex
- 对[k+1,n-1]区间处理前缀mex
- 合并两部分结果
注意：查询[0,n-1]区间时可直接返回n，避免额外查询
3. 完整代码实现与优化
3.1 数据结构设计
使用三个数组维护关键信息：
- bj[]：记录确定的位置
- l[]和r[]：记录每个数字的可能位置范围
int bj[30005], l[30005], r[30005]; bool filled[30005]; // 标记已确定的数字3.2 核心算法流程
- 初始化所有数组值为边界条件
- 从后向前扫描处理后缀mex
- 从前向后扫描处理前缀mex
- 填充未被直接确定的数字
vector<int> perm(int n) { // 初始化代码... // 处理后缀mex for(int i=n-1; i>=0; i--) { int u = qiu(0, i); if(u) r[u-1] = min(r[u-1], i); // 其他处理逻辑... } // 处理前缀mex // ... // 填充剩余数字 for(int i=0; i<n; i++) { if(!filled[i]) { for(int j=l[i]; j<=r[i]; j++) { if(bj[j] == -1) { bj[j] = i; break; } } } } // 返回结果 vector<int> res; for(int i=0; i<n; i++) res.push_back(bj[i]); return res; }4. 常见问题与调试技巧
4.1 典型错误排查
- CE错误：忘记使用
using namespace std; - WA错误：未正确处理边界条件，特别是0的位置
- TLE错误：进行了不必要的mex查询
4.2 调试建议
- 对小规模案例(n≤10)进行手动模拟
- 打印中间变量检查l[]和r[]数组的正确性
- 验证每个数字的位置是否在其允许的范围内
重要提示：在本地测试时，建议先实现一个模拟的query函数，用已知排列验证算法正确性
5. 算法复杂度分析
- 时间复杂度：O(n²) - 最坏情况下需要双重循环填充数字
- 空间复杂度：O(n) - 使用了多个线性数组
- 查询复杂度：严格满足不超过n次查询的要求
6. 扩展思考与优化方向
- 是否可以优化到O(nlogn)时间复杂度？
- 如何处理带限制条件的变种问题？
- 如何将该思路应用于其他排列构造问题？
实际编码中发现，正确初始化数组边界值至关重要。我在首次提交时因为将r[]数组初始化为0而非n-1，导致部分测试用例失败。建议在初始化阶段将所有可能用到的数组元素都显式设置合理的初始值。
对于不确定的数字填充，采用从左到右扫描其允许范围并填入第一个可用位置的方法，在实践中证明是可靠且高效的。相比随机填充，这种方法能保证结果的确定性，便于调试。