AT_arc129_a [ARC129A] Smaller XOR

简要题意

给你三个数 ，询问满足 且 的整数 的个数。

策略分析

我们考虑异或运算的性质，当某一位为 时，它异或一个值可能增大或者不变，当某一位为 时，它异或一个值可能减小或不变，也就是说一个数 想要满足异或一个 要比自己原来小，那么 最高位的数值要是 ，且刚好要能对的上 最高位那个 。只要这一位变成 了，后面 的其它位想怎么取就怎么取，总之不管怎么取都一定比原来的数小。那么假设 的第 位为最高位，根据前面的分析， 就可以满足条件，又因为 ，二者取个交集即可。

上面我们讨论了能够得到 的个数的性质，下面就把它套用在本题上。我们从 的最低位开始扫，每当扫到一个 就对以这一位为最高位的数计算一下 的个数，然后累加起来就是本题的答案。

参考代码

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
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

namespace SHAWN {
    LL n, l, r, ans; 
    int work()
    {
        cin >> n >> l >> r;
        for (int i = 0; (1ll << i) <= n; ++i) {
            LL xl = 1ll << i, xr = (xl << 1) - 1;
            if (!(xl & n)) { continue; }
            LL edgel = max(l, xl), edger = min(r, xr);
            ans = max(ans, ans + edger - edgel + 1);
        }
        cout << ans << '\n';
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}