网站建设哪家好推荐万维科技,hao123手机浏览器,新建站点的步骤,做资讯网站要什么手续来源#xff1a;牛客网 #xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
64bit IO Format: %lld文章目录题目描述题解#xff1a;代码#xff1a;题目描述
有一只可爱的兔子被困在了密室了牛客网
时间限制C/C 1秒其他语言2秒
空间限制C/C 32768K其他语言65536K
64bit IO Format: %lld文章目录题目描述题解代码题目描述
有一只可爱的兔子被困在了密室了密室里有两个数字还有一行字 只有解开密码才能够出去。 可爱的兔子摸索了好久发现密室里的两个数字是表示的是一个区间[L,R] 而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。 比如给了区间[2,5] 那么就有2 3 4 5这些数其中 2 xor 57最大 所以密码就是7。 兔子立马解开了密室的门发现门外还是一个门而且数字越来越大兔子没有办法了所以来求助你。 提示异或指在二进制下一位位比较相同则 0 不同则 1 例如2(010) 2 5(101)2 所以2 xor 5(111)27 输入描述: 第一行一个数 T表示数据组数。 接下来 T 行每行两个数 LR, 表示区间[L,R]。 输出描述: 输出共T行每行一个整数表示[L,R]的密码。 示例1 输入 复制
5
1 10
2 3
3 4
5 5
2 5输出 复制
15
1
7
0
7备注: 对于30%的数据 1 ≤ T ≤ 10 0 ≤ L ≤ R ≤ 100 对于另外10%的数据 LR 对于70%的数据 1 ≤ T ≤ 10 0 ≤ L ≤ R ≤ 50000 对于100%的数据 1 ≤ T ≤ 10000 0 ≤ L ≤ R ≤ 1018 (对于100%的数据) 输入数据较大请使用快速读入。
题解
不同异或为1 要使得两个数异或后的结果最大二进制状态下就要从高位开始就尽量大也就是两个数从高位起尽可能不相同 当L R时return 0 当LR时看L和R最高二进制位是否相等 如果相等在L~R之间的数这一位都是一样的不会对答案有影响继续往后推看下一位。 如果不相等R的这一位一定是1L的这一位肯定是0从这一位往后我们就可以根据R的情况来决定另一个要与R异或的数我们称这个数为x从这一位开始x的之后每一位可以任取x一定大于等于L那么之后取得数都可以实现互补一个取0一个取1异或出来都是1 假设最高是2 i 我们就可以选取2 i和2 i-1这两个数去异或得到的答案就是2 i1-1 所以答案就是L和R二进制不相同的最高位开始之后都是1就是答案
求一次是Olog n
代码
#includebits/stdc.h
using namespace std;
const int maxn1e610;
int size[maxn];
int a[maxn],sum;
vectorintg[maxn];
typedef long long ll;
int n;
inline ll read()
{ll f1,x0;char cgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){x(x1)(x3)(c^48);cgetchar(); }return f*x;}
int main()
{ll t;tread();while(t--){ll lread(),rread();int i;for(i63;i0;i--){if((li)!ri)break;}cout(1lli1)-1endl;}return 0;
}
