1 条题解
-
0
解题思路
两个数的异或结果在第 位上为 ,当且仅当它们在这一位上的值不同(即一个为 ,另一个为 )。
我们可以确定,如果 与 的差值大于等于 ,那么一定可以找到两个数,使得它们在 位上的值不同,并保证解的其他部分成立。这是因为第 位的状态每 个数变化一次。当差值小于 时,我们使用另一个关键观察:在长度为 的连续块内,第 位为 和 的序列是连续的。因此,我们只需检查 与 在第 位上的值是否不同。如果不同,则我们可以将 加入答案。
重复上述过程,直到 大于 。
C++ 代码实现
#include <bits/stdc++.h> using namespace std; int main() { long long l, r; cin >> l >> r; long long ans = 0; long long bit = 1; // 我们实际上只需要找到 l 和 r 的公共前缀之后,第一个不同的位 // 更简单的方法:找到 l 和 r 从最高位开始第一个不同的位 long long x = l ^ r; // 找到 x 的最高位,答案就是 (1 << (最高位+1)) - 1 while (x) { ans = (ans << 1) | 1; x >>= 1; } cout << ans << '\n'; return 0; }
- 1
信息
- ID
- 6785
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者