这道题目就是纯纯的题面搞人心态,看到\(63\)次操作真的很容易想到从高位到低位一位位进行操作。然而正解却不是
先来看官解
首先每次操作只会将\(n\)变小,所以如果\(m>n\),那么肯定无解;如果\(m=n\)那么不用操作;接下来假定\(m<n\)
如果\(m\)最高位\(1\)和\(n\)最高位\(1\)一样,那么直接令\(y=m,n=y\)即可
如果\(m\)最高位\(1\)在\(n\)次高位\(1\)之后(也可以刚好在次高位\(1\)的位置),那么我们令\(y\)为\(2^b-1\),其中\(b\)是次高位\(1\)所在位置。比如\(n=1001000\),则\(y=1111\)(相当于把次高位\(1\)及其后面的所有位全部变成\(1\)),然后令\(n=y\)。如果此时\(m=n\)那么不用再操作,否则的话就转换为了上一种情况
如果\(m\)最高位\(1\)在\(n\)最高位\(1\)和\(n\)次高位\(1\)之间,那么此时无解,官方解答给出了一个reason,但是看不太懂。。。下面我会说我的证法
然后说说我的想法
很自然的一个想法就是从高到低地考虑,我们还是直接假设\(m<n\)
如果\(m\)最高位\(1\)对应的\(n\)的位为\(1\),那么令\(y=m,n=y\)即可
如果\(m\)最高位\(1\)对应的\(n\)的位为\(0\),那么我们考虑\(n\)比这更高的位的\(1\)的个数
如果\(1\)的个数超过一个,那么我们任取其中两个\(1\),令更高位的\(1\)所对应的位置赋\(0\),更低位的\(1\)所对应的位置赋\(1\),然后再将\(m\)最高位的\(1\)的位置赋\(1\),然后把刚刚得到的数令成\(y\),然后令\(n\)与\(y\)异或,这样\(m\)的最高位就和\(n\)的最高位一样了,就像前面一样操作就好了
如果\(1\)的个数只有一个,那么此时无解,因为如果有解,那么对某种操作序列,一定会存在某次操作,将\(m\)的最高位所对应的\(n\)的位置变成\(1\),即\(y\)在\(m\)的最高位这里要取\(1\),根据题目,此时\(y\)在\(n\)的最高位无论取\(1\)还是\(0\)都是不行的(假设此次操作的时候,\(n\)的更高位仍然只有一个\(1\)),所以我们一定会在这种操作的前面将\(n\)的更高位变成两个\(1\),相当于就是将\(n\)的某一位\(0\)变成\(1\),其实就是上面的过程,然后你会发现就循环论证了,所以不可能
标签:Solo,那么,高位,Break,Version,如果,操作,最高,对应 From: https://www.cnblogs.com/dingxingdi/p/18053012