链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
有一只可爱的兔子被困在了密室了,密室里有两个数字,还有一行字:
只有解开密码,才能够出去。
可爱的兔子摸索了好久,发现密室里的两个数字是表示的是一个区间[L,R]
而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。
比如给了区间[2,5] 那么就有2 3 4 5这些数,其中 2 xor 5=7最大 所以密码就是7。
兔子立马解开了密室的门,发现门外还是一个门,而且数字越来越大,兔子没有办法了,所以来求助你。
提示:异或指在二进制下一位位比较,相同则 0 不同则 1
例如2=(010)22=(010)_22=(010)2 5=(101)25=(101)_25=(101)2
所以2 xor 5=(111)2=75=(111)_2=75=(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%的数据) 输入数据较大,请使用快速读入。
这题也是挺巧妙的,完全没想到,只能说学习学习吧。
从第一位开始对比 l 和 r 的二进制数,直到遇到不同的位,构造两个二进制数,一个前几位相同的加上0剩下的全是1,另一个前几位相同的加上1剩下全是0。构造的两个二进制数都在 l 和 r 的范围内,且异或值最大
- #include<bits/stdc++.h>
- using namespace std;
- int t;
- long long l,r;
- long long ksm(int a,int b) {//快速幂
- long long tmp=a,ans=1;
- while(b){
- if( (b & 1) == 1) ans*=tmp;
- tmp*=tmp;
- b>>=1;
- }
- return ans;
- }
- long long read(){//快读
- long long x=0;
- int f=1;
- char ch=getchar();
- while(ch<'0'||ch>'9'){
- if(ch=='-') f=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9'){
- x=x*10+ch-'0';
- ch=getchar();
- }
- return x*f;
-
- }
- int main(){
- scanf("%d",&t);
- while(t--){
- l=read();
- r=read();
- if(l==r){
- cout<<0<<endl;
- continue;
- }
- string a,b;
- while(r){
- b+=r%2+'0';
- r/=2;
- a+='0';
- }
- int cnt=0;
- while(l){
- a[cnt++]=l%2+'0';
- l/=2;
- }
- int idex;
- for(int i=a.size()-1;i>=0;i--){
- if(a[i]!=b[i]) {
- idex=i;
- break;
- }
- }
- for(int i=idex-1;i>=0;i--){
- a[i]='1';
- b[i]='0';
- }
- long long ans=0;
- for(int i=0;i<a.size();i++){
- if(a[i]!=b[i]) ans+=ksm(2,i);
- }
- cout<<ans<<endl;
- }
- }
wa的原因:
没用快速幂