程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 484A Bits

CodeForces 484A Bits

編輯：C++入門知識

CodeForces 484A Bits

題意：

10000個詢問每個詢問輸入L和R（10^18）輸出在區間內二進制表示下1最多的數字如果1個數相同輸出最小的

思路：

YY一下覺得後幾位全是1的時候能保證1的個數多那麼如何構造出這個數字呢？？

將L和R都變成二進制從高位到低位 L和R相同的那幾位一定是不變的因為要保證構造出的數字在區間內然後分兩種情況

一是L和R一直相同那就沒什麼好說的了就是它了

二是發現了有一位不同這時R的那個位一定是1 L的一定是0 那麼只要把R的那個1變成0 然後把後面的所有位都變成1就構造出了數字這時一定1最多嗎？？不一定比如 R=101111 L=100000 構造出來是100111 這時要特判一下如果把差異的那一位變回1是不是超過R 不超過的話變回來更優

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;

int main() {
    int n;
    LL l, r, ans;
    scanf("%d", &n);
    while (n--) {
        cin >> l >> r;
        ans = 0;
        for (int i = 61; i >= 0; i--) {
            if ((r & (1LL << i)) && !(l & (1LL << i))) {
                ans |= (1LL << i);
                ans--;
                if (ans + (1LL << i) <= r)
                    ans += (1LL << i);
                break;
            } else {
                if (r & (1LL << i))
                    ans |= (1LL << i);
            }
        }
        cout << ans << endl;
    }
    return 0;
}