【每日一题】兔子的区间密码
兔子的区间密码
https://ac.nowcoder.com/acm/problem/20860
题目
题目描述：有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：
只有解开密码，才能够出去。
可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[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）知识点
- 这道题其实不难，只是要对这个区间有一个理解。这是一个简单的位运算。要注意的就是二进制位怎么比较与存取。
2）看题目
- 这道题目的意思就是说，求在一个区间里面取任意两个数的最大异或值。
3）算法分析
- 首先我们明确一个观点，越高的数位不同，得到的数字也就越大（就是异或的特性，不同则留下，相同则归零）。
- 这个时候我们就可以注意到，区间的两头分别是最大值和最小值，也就是说判断两端的情况就知道最高位是否相同了。
- 所以我们这个时候就可以分成两种情况来讨论：
- 最高位（指二进制1所在的最高位置）是相同的：这个时候最高位就不重要了，因为不管取哪两个，结果都会把最高位的1抵消了。所以这个时候直接把最高位删除。
- 那如果最高位是不同的：这个时候就说明 l < 2i 而且 r > 2i ，这个时候最大的异或值就是2i ^ 2i - 1 = 2i+1 - 1（为什么？因为10……0和01……1异或时全都不一样，肯定最大呀）。
- 这就是结果了。
4）算法操作
- 这里我们注意一下特殊情况，左右相等直接为0：
if (l == r) { cout << 0 << endl; continue; } - 还有左右不等的判断方法就好了，没有必要求出最高位什么的，直接从二进制上限遍历下来就好了：
for (int i = 59; i >= 0; i--) { if ((l & (1ll << i)) != (r & (1ll << i))) { cout << (2ll << i) - 1ll << endl; break; } if (l & (1ll << i)) { l ^= 1ll << i; r ^= 1ll << i; } }
5）打代码
- 打代码！
- 还是先输入。
- 然后进行循环进行遍历情况。
- 看我代码咯~
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
ll l, r, ans;//区间左右边界和答案
//全局变量区
int main() {
IOS;
int T; cin >> T;
while (T--) {
cin >> l >> r;
if (l == r) {
cout << 0 << endl;
continue;
}
for (int i = 59; i >= 0; i--) {
if ((l & (1ll << i)) != (r & (1ll << i))) {
cout << (2ll << i) - 1ll << endl;
break;
}
if (l & (1ll << i)) {
l ^= 1ll << i;
r ^= 1ll << i;
}
}
}
return 0;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
字节跳动公司氛围 539人发布
查看26道真题和解析