Codeforces 484A Bits：區間內 1 比特數最大的最小數構造

Codeforces 484A Bits：區間內 1 比特數最大的最小數構造

給定區間 [l, r]（0 ≤ l ≤ r ≤ 10¹⁸），找 x ∈ [l, r] 使二進制中 1 的個數（popcount）最大；若多個，取**最小**的 x。多查詢（q ≤ 10⁴）。

核心觀察：貪心構造「盡可能多的低位 1」

要在 [l, r] 內最大化 popcount，應嘗試將**高位保持與 r 相同**，在**第一個 l 與 r 不同的位**上取 0，其後**所有低位置 1**。這樣得到的數：

• ≤ r（因在第一個差異位取 0，r 為 1）。
• ≥ l（因高位同 r ≥ l，且低位全 1 ≥ l 的低位）。
• popcount 極大（低位全 1）。
• 若該數 < l，則在差異位也取 1（即完全同 r），但此時 r 本身即為答案。

算法步驟

1. 將 l, r 轉為二進制陣列（高位在前）。
2. 從高位向低位找第一個 l[i] != r[i] 的位置 pos。
3. 構造答案：ans[0…pos-1] = r[0…pos-1]，ans[pos] = 0，ans[pos+1…] = 1。
4. 若 ans < l，則 ans = r（即差異位也取 1，低位同 r）。

完整 C++ 實現

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q; cin >> q;
    while (q--) {
        int64 l, r; cin >> l >> r;
        if (l == r) { cout << l << '\n'; continue; }
        int bl[64] = {}, br[64] = {}, ans[64] = {};
        int n = 0;
        for (int i = 63; i >= 0; --i) {
            bl[n] = (l >> i) & 1;
            br[n] = (r >> i) & 1;
            ++n;
        }
        int pos = -1;
        for (int i = 0; i < n; ++i)
            if (bl[i] != br[i]) { pos = i; break; }
        // 構造候選
        for (int i = 0; i < pos; ++i) ans[i] = br[i];
        ans[pos] = 0;
        for (int i = pos + 1; i < n; ++i) ans[i] = 1;
        // 轉回數值
        int64 cand = 0;
        for (int i = 0; i < n; ++i) cand = (cand << 1) | ans[i];
        if (cand < l) cand = r;  // 回退到 r
        cout << cand << '\n';
    }
    return 0;
}

示例驗證

查詢：1 10
l=1 (0001), r=10 (1010)
第一差異位：最高位 (8's place) l=0, r=1 → pos=0
構造：ans[0]=0, 低位全1 → 0111 = 7
7 ∈ [1,10], popcount=3 (最大) → 答案 7 ✓

查詢：2 4
l=2 (0010), r=4 (0100)
差異位：4's place l=0,r=1 → 構造 0011=3 ∈ [2,4], popcount=2 → 答案 3 ✓

複雜度

• 單查詢：O(64) 位操作，極快。
• 總體：O(q·64)，q=10⁴ 瞬間完成。

總結

CF 484A 是位運算貪心構造的經典：在 [l, r] 區間內，最大化 popcount 等價於「盡可能保持高位同 r，首個差異位取 0，其後全置 1」。若構造出的數 < l，說明 r 本身已是最優解。無需 DP、無需枚舉，純位操作 O(1) 解決。