自动搬运

查看原文

来自洛谷，原作者为

	xuanxuan001 生活就像愤怒的小鸟，失败后总有几只猪在笑。

搬运于2025-08-24 23:12:42，当前版本为作者最后更新于2025-04-15 16:19:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没人写题解，来写一篇，懒得扯闲话，就不扯了。来个人发篇 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$ 需要满足：

• $\sum\limits_{i=1}^n d_i = 0$
• $d$ 的前缀和两两不同。
• $d$ 的前缀和的极差恰好为 $n-1$（加上前面那条也就是恰好分布在一个连续的区间上）。

发现这三个限制实际上都很强，因此大胆猜想可以唯一确定 $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$ 了。