题解：P15652 [省选联考 2026] 排列游戏 / perm
cosf
·
·
题解
太难了……要是没有特殊性质，我就做不出来了……
算法 1
枚举 i = 0, \dots, (n - 1)，把 i 的位置算出来。i = 0 的时候我们可以直接枚举前缀，如果某一次的 \text{mex} 非零，说明这个是 0 的位置。其他 i 也是类似的（不过要判断 i 是否被 \lt i 的包含）。使用二分优化即可做到 n\log_2 n，期望得分 28 分。
算法 2
考虑 A 性质。此时任何非前缀的子串 \text{mex} 都是 0。考虑把所有前缀问出来，设 s_i 表示 p_0, \dots, p_i 的 \text{mex}。如果 s_i \ne s_{i + 1}，说明 p_{i + 1} = s_i。
这样只能确定一部份数的位置，剩下的数没有固定的位置限制。不过，对于一个 i，我们要确保 i 右侧有一个 \lt i 的数，否则就会有区间的 \text{mex} 等于它了。
显然越大的数限制越小，所以直接从小到大贪心放入即可。期望得分 38 分。
算法 3
考虑 B 性质。如果我们知道了 0 的位置 \mathit{zp}，那么对于任意的 i \ge \mathit{zp}，p_0 到 p_i 的 \text{mex} 就是 p_{i + 1}。
## 算法 $4
可以发现，如果知道了 0 的位置，我们将 0 和之前的数视为一个整体，那么问题就变成了 A 性质。然后再将 0 和之后的视为整体，前缀的数就变成了倒过来的 A 性质。
于是问一些前缀的 \text{mex} 和一些后缀的 \text{mex} 即可得到整个序列。询问次数 n + \log_2 n，期望得分 88.5 分。
算法 5
其实我们并不需要一开始就知道 0 的位置。我们可以直接对于 i = n - 1, \dots, 0，询问 p_0 到 p_i 的 \text{mex}，如果某次 \text{mex} = 0，说明此时的 i + 1 就是 0 的位置。在这之后询问后缀即可。
询问次数 n + O(1)，期望得分 96。
算法 6
整个序列的 \text{mex} 是 n，据此可以优化掉 O(1) 次询问，期望得分 100。