【每日一题】兔子的区间密码 题解

Description

有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：
只有解开密码，才能够出去。
可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[L,R]
而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。
比如给了区间[2,5] 那么就有2 3 4 5这些数，其中 2 xor 5=7最大 所以密码就是7。
兔子立马解开了密室的门，发现门外还是一个门，而且数字越来越大，兔子没有办法了，所以来求助你。

Solution

注意到如果给定两个数字，他们的二进制为
1111
1101
那么显然对于前两位，在这个区间上都是1，那么我们最终构造的必不可能在这两位中取得贡献。
注意到第三位，各不相同，说明可以通过构造得到这一位的贡献，以此类推，只需要找所有位的贡献即可。

Code

import math

def solve(L, R):
    p = (L ^ R);
    ans = 0;
    while p:
        ans = (ans << 1 | 1);
        p >>= 1;
    return ans;

while True:
    try:
        T = int(input());
        for t in range(T):
            L, R = map(int, input().split());
            print(solve(L, R));        
    except EOFError:
        break