兔子的区间密码
兔子的区间密码
https://ac.nowcoder.com/acm/problem/20860
题意:
有一只可爱的兔子被困在了密室了,密室里有两个数字,还有一行字:
只有解开密码,才能够出去。
可爱的兔子摸索了好久,发现密室里的两个数字是表示的是一个区间[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
题解:
首先我们让l r直接xor一下
假设
l 二进制 1010
r 二进制 1100
那么两者xor会得到 0110的结果
发现最高位发生了变化 你会发现 最大值是 0100 xor 0011
这两个值是怎么来的呢,是x 于 y 异或后的最高位 和 异或后得出的结果
当然如果两者最高位不相同,那么异或后的最高位肯定是那个较大的数的最高位。
如果异或后的最高位是i,那么结果就是.
/*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stdlib.h> #include <queue> #include <string> const int maxn = 60; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const int mod = 1e9+7; using namespace std; int main(){ int t; cin>>t; while(t--){ ll x,y; scanf("%lld%lld",&x,&y); ll temp=x^y; ll ans=1; while(temp){ temp/=2; ans*=2; } printf("%lld\n",ans-1); } }
题解 文章被收录于专栏
主要写一些题目的题解