题解：P11355 [eJOI2023] Teleporters

nullqtr_pwp · 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)。

提交记录。