自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

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

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

以下是正文

Solution 1

$s=t$ 时答案显然为 $0$，只需要考虑 $s \ne t$ 时的情况。

断言：将 $s$ 的值先修改为 $2^n-1$ 再修改为 $t$ 一定不劣。

证明：首先这样显然是满足两个限制条件的，所以我们可以这样操作。接下来，对于每个二进制位，设 $s$ 中该位为 $a$，$t$ 中该位为 $b$，则我们可以根据 $a$ 和 $b$ 的值分类讨论，得到必须进行的操作：

• 若 $a=b=0$，由于第二条限制，必须先将 $a$ 的值修改为 $1$ 再修改为 $0$。
• 若 $a=0$，$b=1$，则必然会将 $a$ 的值修改为 $1$ 至少一次。
• 若 $a=1$，$b=0$，则必然会将 $a$ 的值修改为 $0$ 至少一次。
• 若 $a=b=1$，则没有必须进行的操作。

我们发现「将 $s$ 的值先修改为 $2^n-1$ 再修改为 $t$」只进行了必须进行的操作，只会付出进行这些操作的代价，于是证明了这样操作一定不劣。

当然，还有其他的证明方式同样可以得到该结论。

根据结论，我们直接输出 $(s \oplus (2^n-1))+((2^n-1)\oplus t)$ 即可。

Solution 2

由于需要满足 $s \cup x = 2^n-1$，所以 $s$ 和 $x$ 在每个二进制位中至少需要有一位为 $1$；
由于代价为 $s \oplus x$，所以 $s$ 和 $x$ 在二进制下相同的位数越多越好。

所以对于所有满足条件的 $x$，$x=2^n-1$ 时代价最小。

$s=t$ 时输出 $0$，否则判断一下是否能一步从 $s$ 变到 $t$，和 $s$ 变到 $2^n-1$ 再变到 $t$ 的代价取个 $\min$ 即可。

其实可以证明，从 $s$ 变到 $2^n-1$ 再变到 $t$ 一定不比直接从 $s$ 变到 $t$ 劣，但是不知道也已经能做了。