自动搬运

查看原文

来自洛谷，原作者为

	nullqtr_pwp 我注意到有些人一直在做各种地方的cnoi题，但是并没有什么b用，可能是因为一直在舒适区里面舒服的卷，虐杀自己擅长的东西并获得成就感。

搬运于2025-08-24 23:06:40，当前版本为作者最后更新于2024-12-12 08:54:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先考虑任意 $f$ 全部相同且给定一些允许使用的传送器，如何判定是否可达。我们可以在操作间寻找一些兼而有之的操作量，本题可以选择从 $A-B$ 的值入手。注意到一次变换相当于选定一个合法的 $c$，将坐标 $x$ 变换为 $2c-x$。此时两者差原来为 $d=x_2-x_1$，会变换为 $2(c_2-c_1)-d$。注意到两者完全对称，可以取相反数。即增加了 $2(c_1-c_2)$。 实际操作中就是 $p,q$ 的顺序可以换。问题转化为是否可以选择若干组数对 $(c_{1,i},c_{2,i})$，由 $d=A-B$ 变换到 $0$。判掉奇偶错误的情况并除以 $2$ 之后，考虑使用贝祖定理，这要求所有 $(c_i,c_j)$ 的差分值的 $\gcd$ 是 $d$ 的因子。上述运算均取绝对值。这样你就可以暴力判了。

注意到 $\gcd(a,b)=\gcd(a,a+b)$，那么你将 $(i,j)$ 视为一条边，判定所有差分值的 $\gcd$ 只需要一棵生成树，也就是说顺序是无关紧要的。因此你可以随便打乱顺序然后取相邻数差分的 $\gcd$。这样信息量就正确了。可以按照 $f$ 进行排序，这样能用的传送器就是一个区间，你可以快速求差分数组的 $\gcd$ 来进行判定。

考虑正解。最大化最小值可以使用二分答案。你发现在上述过程中，跳相邻的数就可以了，这样在有解的前提下也最小化了 $\max|f_p-f_q|$。因此二分 $mid$ 时只需要加入差值 $\leq mid$ 的相邻数对的差分。线段树求一下这个区间的合法位置的 $\gcd$。多组询问怎么做，套个整体二分即可。时间复杂度 $\mathcal O(n\log^2n)$。

提交记录。