Codeforces 164E Compatible Numbers 狀態壓縮 DP 優化

Codeforces 164E Compatible Numbers 題目解析

給定 n 個數 (≤10⁵)，每個數 ≤ 4×10⁶ (22 位)。對每個數 aᵢ，找另一個數 aⱼ 使 aᵢ & aⱼ = 0。若不存在輸出 -1。暴力 O(n²) 超時。

核心洞察：超集 DP / SOS DP

aᵢ & aⱼ = 0 ⇔ aⱼ ⊆ ~aᵢ (在 22 位範圍內)。即 aⱼ 是 aᵢ 取反的子集。預處理：對每個掩碼 m，記錄是否存在數等於 m 的超集。從大掩碼向小掩碼遞推：dp[mask] = dp[mask] || dp[mask | (1<<i)]。

算法流程

1. 全 1 掩碼 S = (1<<22) - 1
2. 對每個輸入 x，設置 dp[x ^ S] = x (x 的互補掩碼記錄 x)
3. 從 S 遞減到 0 枚舉掩碼：若 dp[mask] 為空，嘗試從添加一位的超集繼承值
4. 查詢：對每個 x，輸出 dp[x] (即與 x 兼容的某個數)

C++ 代碼實現

#include <iostream>
#include <cstring>
using namespace std;

const int MX = (1 << 22) + 5;
int n, dp[MX], g[MX];

int main() {
    while (~scanf("%d", &n)) {
        int S = (1 << 22) - 1;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; ++i) {
            scanf("%d", &g[i]);
            dp[g[i] ^ S] = g[i];  // 記錄互補掩碼對應的值
        }
        for (int i = S; i >= 0; --i) {  // 從大到小枚舉掩碼
            if (!dp[i]) {
                for (int j = 0; j < 22; ++j)  // 嘗試添加一位
                    if (dp[i | (1 << j)])
                        dp[i] = dp[i | (1 << j)];
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i) cout << " ";
            if (dp[g[i]]) cout << dp[g[i]];
            else cout << "-1";
        }
        cout << endl;
    }
    return 0;
}

複雜度分析

• 時間：O(22 × 2²² + n) ≈ 9.2×10⁷ 操作，1 秒內可通過
• 空間：O(2²²) ≈ 4M int ≈ 16MB
• 關鍵優化：從大到小枚舉 + 位添加繼承，實現超集 DP

易錯點

• 掩碼大小：數據 ≤ 4×10⁶ < 2²²，需 22 位
• 互補掩碼：x ^ S 而非 ~x (避免符號位)
• 遞推方向：從大掩碼到小掩碼 (超集到子集)
• 多解任輸出一個：繼承任意超集值即可