HDU 5969 bitset + 思维

发表于 分类于 阅读次数：

思维，不太好想感觉。

链接

思路

我们先将两个边界设置为bitset类型，然后从高位开始枚举，如果两个数的二进制数在这一位相等，那么肯定这一位也只能选这个数字了，如果不相等，肯定是L边界这一位为0， R边界这一位为1，那么这样的话这一位就是1了，剩下的也都是1了，因为我们可以选择的数字是这一位为0，后边全为1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
typedef long long ll;


int main()
{
    int T;
    long long l, r;
    cin >> T;
    while(T--)
    {
        cin >> l >> r;
        bitset<64> b(l);
        bitset<64> c(r);
        ll sum = 0;
        for(int i = 63; i >= 0; --i)
        {
            if(b[i] == 0 && c[i] == 1)
            {
                sum += (ll)pow(2, i + 1) - 1;
                break;
            }
            else{
                if(b[i] == 1)
                sum += (ll)pow(2, i);
            }
        }
        cout << sum << '\n';
    }
}