题解：P15652 [省选联考 2026] 排列游戏 / perm

· · 题解

MEX（Minimum Excluded Element），即集合中未出现的最小自然数。

对于 0\sim n-1 的排列 p，注意到 \operatorname{mex}_{i\in [l,r]}(p_i)=\operatorname{min}_{i\notin [l,r]}(p_i)。

证明：记 \operatorname{mex}_{i\in [l,r]}(p_i)=x。由定义，[l,r] 内存在 0\sim x-1 不存在 x，因此 [l,r] 外不存在 0\sim x-1 存在 x。故 \operatorname{min}_{i\notin [l,r]}(p_i)=x。

而 \operatorname{min}_{i\notin [l,r]}(p_i) 等于 [0,l) 前缀的最小值与 (r,n-1] 后缀的最小值的较小值。取 l=0 与 r=n-1，可以说明，若一个排列被判定为正确，则此排列与隐藏排列的前/后缀最小值序列必须相同。容易发现这个条件也是充要的。

于是问题化为两部分：求出隐藏排列的前/后缀最小值共 2n 项；构造一个满足前/后缀最小值的排列。

先看构造。对于前/后缀最小值发生变化的的地方，排列的值是确定的。令前/后缀最小值为 pre_i/suf_i，若 pre_i\neq pre_{i+1} 则 p_{i+1}=pre_{i+1}，对 suf 同理。

对于未确定的位置，其只有限制条件 p_i\ge pre_i，p_i\ge suf_i。将这些位置按 \max\{pre_i,suf_i\} 排序，然后从小到大填入未使用的数即可。构造的时间复杂度为 O(n\log n)。

现在需要求出前/后缀最小值序列。

算法 1

可以询问前缀 \operatorname{mex} 获得后缀 \operatorname{min}，询问后缀 \operatorname{mex} 获得前缀 \operatorname{min}。直接询问 2n-2 次（n 项的前/后缀不用询问）。期望得分 65.2083。

算法 2

如果知道 0 的位置，那么就可以确定前/后缀最小值中的 n+1 项 0，再询问 n-1 次即可。求 0 的位置可以二分，区间里有 0 当且仅当 \operatorname{mex} 不为 0。共 n-1+\lceil\log_2 n\rceil 次询问，期望得分 83.8892。

算法 3

依次询问长为 0,1,2,\dots 的前缀的最小值，直到出现首个 0，就知道了 0 的位置。剩余的后缀只需询问后缀最小值即可。询问次数 \le n，期望得分 100。