1 条题解

  • 0
    @ 2024-6-6 18:50:55

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

    #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;
    }
    
    • 1

    信息

    ID
    956
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    18
    已通过
    16
    上传者