1. 题目背景与核心思路解析P15652 [省选联考 2026] 排列游戏是一道考察排列构造与mex函数性质的交互题。题目要求我们通过不超过n次的mex查询构造出一个长度为n的排列使其满足特定的mex条件。核心思路在于利用mex函数的单调性质前缀mex数组s具有非递减特性当s[i] ≠ s[i1]时可以确定a[i1] s[i]对于未被直接确定的数字需要利用mex函数的区间性质确定其可能位置范围2. 关键算法实现细节2.1 特殊情况的处理当0位于排列首位时解法最为直观计算前缀mex数组s对于每个i若s[i] ≠ s[i1]则a[i1] s[i]剩余数字填入任意满足s数组的位置// 示例代码片段 for(int i0; in; 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对[k1,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填充未被直接确定的数字vectorint perm(int n) { // 初始化代码... // 处理后缀mex for(int in-1; i0; i--) { int u qiu(0, i); if(u) r[u-1] min(r[u-1], i); // 其他处理逻辑... } // 处理前缀mex // ... // 填充剩余数字 for(int i0; in; i) { if(!filled[i]) { for(int jl[i]; jr[i]; j) { if(bj[j] -1) { bj[j] i; break; } } } } // 返回结果 vectorint res; for(int i0; in; 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导致部分测试用例失败。建议在初始化阶段将所有可能用到的数组元素都显式设置合理的初始值。对于不确定的数字填充采用从左到右扫描其允许范围并填入第一个可用位置的方法在实践中证明是可靠且高效的。相比随机填充这种方法能保证结果的确定性便于调试。
