[ARC129A] Smaller XOR

yhx0322 · 2023-11-13 20:15:41 · 题解

Description

输入 N,L,R，询问满足 L \le x \le R，并且 (x \oplus N ) < N 的正整数 x 的个数。

Solution

发现一个性质：对于每一位 t，如果需要满足上述条件，二进制下的 t 必须为 1。

于是我们便可以枚举 t，每次 x 的区间为 [2 ^ {t},2 ^ {t + 1})。又因为 L \le x \le R，所以我们取交集即可。

注意：由于本题的数据范围，记得开 long long，并且使用位运算的时候记得将 1 改为 1LL，否则会出错。

Code

#include <bits/stdc++.h>

#define int long long

using namespace std;

int n, l, r, ans;
signed main() {
    cin >> n >> l >> r;
    for (int i = 0; (1LL << i) <= n; i++) {
        int s = 1LL << i, t = (s << 1LL) - 1; // 两个 x 的区间
        if ((s & n) == 0) {
            continue;
        }
        int L = max(l, s), R = min(r, t);
        ans = max(ans, ans + R - L + 1);
    }
    cout << ans;

    return 0;
}