UVA 1326 Jurassic Remains：技巧枚舉 + 位運算求最大合法骨骼子集

問題描述

N ≤ 24 塊骨頭，每塊有若干關節標籤（大寫字母 A-Z）。同字母標籤的關節必須配對連接。選擇最大子集，使得所有標籤出現次數均為**偶數**（可完美配對）。輸出最大數量及編號（1-based，升序）。

核心觀察：位掩碼表示奇偶性

每塊骨頭用 26 位整數表示：第 i 位為 1 表示字母 `'A'+i` 出現**奇數**次（題目保證每塊骨頭同字母最多一次，所以直接置 1）。
選擇若干骨頭，所有標籤出現偶數次 ⇔ 選中骨頭的位掩碼 **異或和為 0**。

技巧枚舉：一分為二

N=24 直接枚舉 2^24 太大。分成兩半：前 n1 = N/2，後 n2 = N-n1。
枚舉前半所有子集 (2^n1 ≤ 2^12=4096)，計算異或和 `mask`，記錄該 `mask` 下**最大選取數**及對應子集（用 `map` 存 `mask → 子集位掩碼`）。
枚舉後半所有子集 (2^n2)，計算 `mask2`，查找前半是否有 `mask1 == mask2`（因 `mask1 ^ mask2 == 0`）。若有，合併兩半子集，更新全局最大選取數。

代碼關鍵部分

int state[24]; // 每塊骨頭的位掩碼
map best; // mask -> 前半子集位掩碼(取最大位數的)

void solve() {
    int n1 = n/2, n2 = n - n1;
    // 前半枚舉
    for (int s = 0; s < (1<>i & 1) mask ^= state[i];
        if (__builtin_popcount(s) > __builtin_popcount(best[mask]))
            best[mask] = s;
    }
    int ans = 0, best1 = 0, best2 = 0;
    // 後半枚舉
    for (int s = 0; s < (1<>i & 1) mask ^= state[i+n1];
        if (best.count(mask)) {
            int total = __builtin_popcount(s) + __builtin_popcount(best[mask]);
            if (total > ans) {
                ans = total;
                best1 = best[mask];
                best2 = s;
            }
        }
    }
    // 輸出 ans 及對應編號
}

複雜度

時間 O(2^(N/2) * N) ≈ 4096 * 24 ≈ 1e5，極快。空間 O(2^(N/2))。

總結

「位掩碼表示奇偶性」+「一分為二枚舉」是解決 N≈24 子集異或和為 0 最大化問題的經典套路。將問題轉化為尋找兩半相同異或和，利用哈希表匹配，完美平衡時間空間。