题解：B3978 [信息与未来 2024] 幸运数字

沉石鱼惊旋 · 2024-06-06 12:46:34 · 题解

一个很小朋友的做法是把每个数转二进制字符串或者用数组存下来判断。这里给一个时间复杂度为 \mathcal O(n\log V) 但空间复杂度为 \mathcal O(1) 的写法：使用位运算，通过 x >> i & 1 获得 x 在二进制下的第 i 位。

#include <bits/stdc++.h>
using namespace std;
int a, b;
int ans;
bool check(int x)
{
    for (int i = 30; i >= 0; i--)
    {
        if ((i < 30 ? (x >> i + 1 & 1) ^ (x >> i & 1) : 1) && (i > 0 ? (x >> i & 1) ^ (x >> i - 1 & 1) : 1))
            return 0;
    }
    return 1;
}
int main()
{
    cin >> a >> b;
    for (int i = a; i <= b; i++)
        ans += check(i);
    cout << ans << endl;
    return 0;
}