1 条题解

  • 0
    @ 2026-5-4 13:01:51

    解题思路

    两个数的异或结果在第 ii 位上为 11,当且仅当它们在这一位上的值不同(即一个为 00,另一个为 11)。
    我们可以确定,如果 RRLL 的差值大于等于 2i2^i,那么一定可以找到两个数,使得它们在 ii 位上的值不同,并保证解的其他部分成立。这是因为第 ii 位的状态每 2i2^i 个数变化一次。

    当差值小于 2i2^i 时,我们使用另一个关键观察:在长度为 2i2^i 的连续块内,第 ii 位为 0011 的序列是连续的。因此,我们只需检查 RRLL 在第 ii 位上的值是否不同。如果不同,则我们可以将 2i2^i 加入答案。
    重复上述过程,直到 2i2^i 大于 RR


    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
    上传者