题解：P12090 [RMI 2019] 秘密排列 / Secret Permutation

· · 题解

没人写题解，来写一篇，懒得扯闲话，就不扯了。来个人发篇 C 题解呗。

首先思考一下所谓的“等价”，发现询问的式子只在两个 v 中取到最小值 n-1，那就是分别满足 p_{v_i} = i 和 p_{v_i} = n-i+1 时，并且不难发现将 p 的所有元素变为 n+1-p_i 后无法用操作区分，所以实际上就是这两个排列等价，但 Sample Grader 为什么不判一下啊，感觉这步很 trivial 啊，没啥保密的必要。

然后考虑 n 次询问，发现计算的这个值其实就是环上去掉一个值，因此如果将一个排列 v 的 n 种循环移位分别问一次就可以直接解出这个循环上的 n 项的值，也就是所有的 a_i = |p_{v_i} - p_{v_{(i \bmod n) + 1}}|。

考虑直接用这 n 个差求出原排列，乍一看可能觉得不太可能，但仔细想想似乎真的可以，相当于确定一个差分数组 d，每个位置需要确定是 d_i = a_i 还是 d_i = -a_i。而一组合法的 d 需要满足：

发现这三个限制实际上都很强，因此大胆猜想可以唯一确定 d，也就是 p，赛时没想到反例，赛后发现了一个：

a={1,2,1,2}
d1={1,2,-1,-2},p1={1,3,2,4}
d2={1,-2,-1,2},p1={4,3,1,2}

这时需要另一次询问来分辨，可能这就是题面中说的“98 分的做法”。

不过继续大胆猜想在 n 较大的时候依然唯一，即使不一定那不唯一的情况也一定极少，并且交互库不自适应，所以只需要在一开始随机生成一个 v 就等于让 p 变成了一个随机排列，这样出错概率很小。

那么基本确定了这个做法的可靠性后再考虑求出 p，也就是找到这个 d。那么还是由于前面的限制很强并且是随机排列，所以可以猜测真正合法的状态很少，因此直接搜索逐位确定选择，每次只找合法的方向继续搜索即可。

赛时我是找到一个直接退出，然后换了个随机种子就 85 \rightarrow 100 了。