Codeforces 484A Bits：區間內二進制 1 最多的數構造法

Codeforces 484A Bits

給定 10^4 個查詢，每個查詢區間 [L, R] (≤10^18)，找出區間內二進制表示中 1 的個數最多的數；若有多個，輸出最小的。

核心觀察

在區間內，使二進制 1 最多的數，通常是「後綴全為 1」的數。構造策略：從高位到低位找到 L 和 R 第一個不同的位（R 必為 1，L 必為 0），將該位設為 0，後面全設為 1，得到候選數。再檢查若將該位改回 1 是否仍 ≤ R，若是則更優。

算法步驟

1. 從高位 (61) 到低位遍歷。
2. 若 R 的第 i 位為 1 且 L 的第 i 位為 0：
3. 構造 ans = R 的高位相同部分 + (1<
4. 若 ans + (1<
5. 跳出循環輸出 ans。
6. 若遍歷結束未發現不同位，則 L=R，直接輸出 L。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    int n; scanf("%d", &n);
    while(n--) {
        LL L, R, ans = 0;
        cin >> L >> R;
        for(int i = 61; i >= 0; i--) {
            LL bit = 1LL << i;
            if((R & bit) && !(L & bit)) {
                ans |= bit; ans--; // 該位置1，後面全1（ans = 高位相同 + 011..1）
                if(ans + bit <= R) ans += bit; // 能改回1更優
                break;
            } else if(R & bit) {
                ans |= bit; // 高位相同部分保留
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

例子演示

• L=100000 (二進制), R=101111：第一個不同位是第 3 位（從高算），構造 100111，檢查 101111 ≤ R 成立，改回 1 得 101111，1 的個數更多。
• L=5 (101), R=6 (110)：不同位在第 1 位，構造 101 (5)，改回 1 得 110 (6) 但 6 有兩個 1，5 有兩個 1，取較小者 5？實際代碼邏輯會正確處理。

複雜度

每查詢 O(62) = O(1)，總時間 O(Q)，極快。

總結

本題展示了位運算構造最優解的技巧：從高位找分歧，構造後綴全 1，再貪心嘗試提升分歧位。這是處理「區間內位運算最優值」問題的通用思路。