「Cfz Round 5」Non-breath Oblige 题解

· · 题解

Solution 1

断言：将 $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$ 劣，但是不知道也已经能做了。