【题解】牛牛异或最大值

题意

给你 $n$ 和区间 $\left [ L,R \right ]$ ，求 $n$ 与区间 $\left [ L,R \right ]$ 中的数异或后的最大值是多少。

题解

考虑什么样的数与 $n$ 异或会最大呢，那么直接贪心的考虑，就是 $n$ 的二进制位下0的地方是1，1的地方是0这样就能保证结果是最大的。
由于题目范围最大是 $2^{32}-1$ ，所以我们需要用无符号整型或者longlong来进行操作，我们从第31位开始遍历，若该位上 $n$ 是 $0$ ，那我们需要和他异或的那个数就应该这位上是1，还需要判断一下若该数加上这位是1的话会不会超过上界 $R$ ，若不超过就加上 $1u<<i$ 。若该位 $n$ 是1的话，我们要异或的这个数就得是0了，但是还需要考虑下界，由于有下界 $L$ 的限制，若该位不是1的话，有可能后续位上都填上1，也会使得该异或的数任小于下界 $L$ ，所以我们判断一下若当该异或的数 $m+(1u<<i)-1<L$ ，即后续都是1的时候仍小于 $L$ 的话必须该位是1。即 $m+(1u<<i)\leq L$ 。两种情况都判断完了就可以写出代码了。

复杂度

时间复杂度为 $O(31)$
空间复杂度为 $O(1)$

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    unsigned int n, L, R, ans;
    while (t--)
    {
        scanf("%u%u%u",&n,&L,&R);
        ans = 0U;
        for (int i = 31; i >= 0; -- i) {
            if ((1U<<i)&n) {
                if (ans + (1U<<i) <= L) {
                    ans = ans + (1U<<i);
                }
            }else {
                if (ans + (1U<<i) <= R) {
                    ans = ans + (1U<<i);
                }
            }
        }
        printf("%u\n",ans^n);
    }
    return 0;
}