题目

B君和G君聊天的时候想到了如下的问题。

给定自然数l和r ,选取2个整数\(x,y\)满足\(l <= x <= y <= r\),使得\(x|y\)最大。

其中\(|\)表示按位或，即\(C、 C++、 Java\)中的\(|\)运算。

输入格式

包含至多\(10001\)组测试数据。

第一行有一个正整数，表示数据的组数。

接下来每一行表示一组数据，包含两个整数\(l,r\)。

保证 \(0 <= l <= r <= 1018\)。

输出格式

对于每组数据输出一行，表示最大的位或。

输入样例

5

1 10

0 1

1023 1024

233 322

1000000000000000000 1000000000000000000

输出样例

15

1

2047

511

1000000000000000000

题解

输入两个数字\(l,r\)

二进制位低位对齐, 从高位向低位遍历.

如果两个数字第\(i\)位不相同, 那答案从这一位开始, 到最后都是\(1\), 然后停止遍历.

因为这步(不相同)会停止遍历, 所以前面每位都相同, 在保持前面不变的情况下, 可以直接忽略前面, 那么, 由于不相同, 必定有一个\(1\), 有一个\(0\).

因为前面都相等, 所以必定是大数这一位为\(1\), 那就是这样的情况:

1xxxxx (大数)

0xxxxx (小数)

如果最终做运算的一个数可以取大数到小数之间的任何数字, 自然也包括011111, 而011111|1xxxxx 答案自然是111111, 后面无需再计算.

如果两个数字的第\(i\)位相同, 答案这一位也相同.

由于遇到第一个不同的数字循环就会停止, 所以前面所有位都相同, 也就没有增减的余地, 这一位加1必定大于最大值, 减1必定小于最小值, 所以不变即可

代码

#include <cstdio>

int main() {

    int t;

    scanf("%d", &t);

    while (t--) {

        long long a, b, ans = 0;

        scanf("%lld%lld", &a, &b);

        for (long long i = 60; i >= 0; i--) {

            if(!((1&(a>>i))^(1&(b>>i)))) ans^=(a&(1ll<<i));

            else{

                ans^=(1ll<<(i+1ll))-1ll;

                break;

            }

        }

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

HDU 5969 最大的位或题解

题目

输入格式

输出格式

输入样例

输出样例

题解

代码

最新文章

热门文章

巴特西

HDU 5969 最大的位或 题解

题目

输入格式

输出格式

输入样例

输出样例

题解

代码

最新文章

热门文章

HDU 5969 最大的位或题解