「Cfz Round 5」Non-breath Oblige 题解

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

劣，但是不知道也已经能做了。

「Cfz Round 5」Non-breath Oblige 题解

文章操作

Solution 1

Solution 2

相关推荐

评论

「Cfz Round 5」Non-breath Oblige 题解