时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：
只有解开密码，才能够出去。
可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[L,R]
而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。
比如给了区间[2,5] 那么就有2 3 4 5这些数，其中 2 xor 5=7最大 所以密码就是7。
兔子立马解开了密室的门，发现门外还是一个门，而且数字越来越大，兔子没有办法了，所以来求助你。
提示：异或指在二进制下一位位比较，相同则 0 不同则 1
例如2=(010) 2 5=(101)2
所以2 xor 5=(111)2=7
输入描述:
第一行一个数 T，表示数据组数。
接下来 T 行，每行两个数 L，R, 表示区间[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%的数据
L=R
对于70%的数据
1 ≤ T ≤ 10
0 ≤ L ≤ R ≤ 50000
对于100%的数据
1 ≤ T ≤ 10000
0 ≤ L ≤ R ≤ 1018
(对于100%的数据) 输入数据较大，请使用快速读入。
题解：
不同异或为1
要使得两个数异或后的结果最大，二进制状态下就要从高位开始就尽量大，也就是两个数从高位起尽可能不相同
当L = = R时，return 0
当L<R时，看L和R最高二进制位是否相等
如果相等在L~R之间的数这一位都是一样的，不会对答案有影响，继续往后推看下一位。
如果不相等，R的这一位一定是1，L的这一位肯定是0，从这一位往后我们就可以根据R的情况来决定另一个要与R异或的数（我们称这个数为x），从这一位开始，x的之后每一位可以任取，x一定大于等于L，那么之后取得数都可以实现互补（一个取0，一个取1），异或出来都是1
假设最高是2 i ，我们就可以选取2 i和2 i-1这两个数去异或得到的答案就是2 i+1-1
所以答案就是L和R二进制不相同的最高位开始之后都是1，就是答案
求一次是O（log n）
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int size[maxn];
int a[maxn],sum;
vector<int>g[maxn];
typedef long long ll;
int n;
inline ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return f*x;
}
int main()
{
ll t;
t=read();
while(t--)
{
ll l=read(),r=read();
int i;
for(i=63;i>=0;i--)
{
if((l>>i)!=r>>i)break;
}
cout<<(1ll<<i+1)-1<<endl;
}
return 0;
}
京公网安备 11010502036488号