刚开始以为是 case 题,结果是性质题。
首先肯定从高到低考虑,现在比较困难的事情就是如何决策到底哪些数占据高位哪些数占据低位。这样分类讨论贼多而且还不好做,出题人肯定不会自己给自己设限,想一写基于性质的做法。
思考为什么全选 \(y\) 不对,本质上是因为有些位置 \(1\) 足够多需要某一个数通过干掉这个位置上的 \(1\) 来满足更低位的 \(1\)。
有一个很强的结论是,如果对于一个数 \(x\) 的二进制下第 \(i\) 位的 \(1\),把它干掉且将低位全部变为 \(1\) 的数能够 \(\ge x\),那么它就能牺牲它一个,幸福所有比它低的位,而且我们发现更低的位是无法贡献给更高的位的,于是最多只可能进行 \(1\) 次这样的操作,并且在限制最紧的情况下贡献是最多的。
对于每一位,判断一下能否贡献即可,显然只会找能贡献的最高的位贡献,不然一定不优。
也就是性质便是,只会有一个数不是 \(y\)。