题解 AT_arc129_a [ARC129A] Smaller XOR

AT_arc129_a [ARC129A] Smaller XOR

简要题意

给你三个数 $N, L, R$，询问满足 $x \in [L, R]$ 且 $(x \oplus N) < N$ 的整数 $x$ 的个数。

策略分析

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

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

参考代码

#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();
}