题意: 给定,在
中选取两个数使得两数异或值最大。
数据范围:
题解: 考虑二进制形式,则二进制的最高位最高越好,同时选取的两个数二进制位不同的部分越多越好。
考虑一个极端情况:即答案的二进制形式为
那么取
,
取
则两者异或答案最大。
这里的为
,则
为
。
对于和
,当两者的二进制最高位相同时,无论怎么选择最高位对最终答案都无贡献,所以考虑将最高位删去后继续考虑,直到存在
的二进制最高位
大于
的二进制最高位
,那么答案就是
,如果删至两者均为
,则答案为
,此时的情况是
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<typename T> inline T Read(){ T s=0,f=1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();} while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();} return s*f; } #define read() Read<int>() #define readl() Read<ll>() int main() { int g = 0; int T = read(); for(int i = 1; i <= T; ++i) { ll l = readl(), r = readl(); int flag = 1; for(int j = 60; j >= 0; j--) { int L = l >> j & 1; int R = r >> j & 1; if(R > L) { printf("%lld\n", (1ll << (j + 1)) - 1); flag = 0; break; } } if(flag) puts("0"); } return 0; }