BZOJ 2460 [BeiJing2011] 元素：貪心 + 線性基（高斯消元）求最大權值子集

問題描述

給定 n 個元素，每個有兩個屬性 a（長整數）和 b（權值）。需選擇一個子集，使得：
1. 子集中任意非空子集的 a 值異或和 ≠ 0（即 a 值線性無關）。
2. 滿足條件 1 下，b 值之和最大。
輸出最大權值和。

核心理論：線性基與貪心

條件 1 等價於：選中的 a 值在 GF(2) 意義下線性無關，即它們構成一個線性基。
經典結論：按權值 b 從大到小排序，依次嘗試插入線性基；若能插入（即不與現有基向量線性相關），則選中該元素，累加權值。此貪心策略正確性可用拟阵理論證明。

線性基維護（高斯消元風格）

維護一個陣列 base[bit]，表示最高位為 bit 的基向量。
插入數 x：
for bit 從高到低（如 62~0）：
  if (x & (1LL << bit)) {
    if (!base[bit]) { base[bit] = x; return true; } // 插入成功
    x ^= base[bit]; // 消去該位
  }
若最終 x == 0，說明線性相關，插入失敗。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
struct Item { long long a; int b; };
bool cmp(const Item& x, const Item& y) { return x.b > y.b; }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector items(n);
    for (auto& it : items) cin >> it.a >> it.b;
    sort(items.begin(), items.end(), cmp);
    long long base[63] = {0};
    long long ans = 0;
    for (auto& it : items) {
        long long x = it.a;
        for (int bit = 62; bit >= 0; --bit) {
            if (x & (1LL << bit)) {
                if (!base[bit]) { base[bit] = x; ans += it.b; break; }
                x ^= base[bit];
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

複雜度分析

• 排序：O(n log n)。
• 插入線性基：每個元素最多 63 位操作，O(n × 63)。
• 總時間：O(n log n + 63n)，空間 O(63)。

關鍵點總結

• 「異或和不為 0 的子集」⇔ 向量線性無關 ⇔ 線性基。
• 貪心選擇最大權值：拟阵性質保證最優。
• 線性基插入即高斯消元過程，代碼極簡。

這題是「線性基 + 貪心」的教科書級例題，展示了抽象代數結構在算法競賽中的強大威力。