HDU 5299 Circles Game：圓的包含關系 + SG 函數 + 掃描線構建森林

問題描述

平面上有 n 個圓，任意兩圓要么包含、要么分離，不相交不相切。Alice 和 Bob 輪流操作：選一個圓並刪除它及其內部所有圓。無法操作者輸。雙方最優策略下，誰獲勝？

核心轉化：圓的包含關系 = 森林

因為圓之間只有「包含」或「分離」，包含關系天然形成一棵或多棵樹（森林）：
父圓直接包含子圓，且無其他圓夾在中間。
操作「選一個圓並刪除它及其內部所有圓」等價於在樹上刪除一個節點及其整棵子樹。

樹上刪子樹遊戲 = SG 函數

經典組合遊戲理論結論（賈志豪《組合遊戲略述》）：

• 葉子節點 SG 值 = 0
• 內部節點 SG 值 = (子節點 SG 值 + 1) 的異或和

整個森林的 SG 值 = 所有樹根 SG 值異或和。
SG ≠ 0 → 先手必勝；SG = 0 → 後手必勝。

關鍵難點：如何 O(n log n) 構建包含森林？

暴力 O(n²) 判斷包含關系會 TLE（n ≤ 20000）。
使用掃描線算法：

1. 每個圓產生兩個事件：x - r（進入），x + r（離開）。
2. 按 x 座標排序所有事件。
3. 掃描線維護一個有序集合（set），按圓在當前 x 位置的 y 座標排序（實際比較器較複雜，需幾何判斷）。
4. 遇到「進入事件」：在 set 中找到其應插入位置，根據鄰居關系確定父子關系，插入 set。
5. 遇到「離開事件」：從 set 中刪除。

代碼框架

struct Circle { int x, y, r; } c[MAXN];
struct Event { int x, type, id; }; // type: +1 進入, -1 離開
// 排序：x 升序，同 x 先進入後離開

// 自定義比較器：比較兩圓在掃描線當前 x 位置的上下關系
struct Comparator {
    int sweepX;
    bool operator()(int a, int b) const {
        // 幾何計算：兩圓在 x=sweepX 時的 y 座標
        // 實際需處理圓心在掃描線左側/右側的情況
    }
};

set s;
vector tree[MAXN]; // 存儲森林邊

void buildForest() {
    // 生成事件、排序
    // 掃描處理
    // 進入時：it = s.lower_bound(id); 根據 it 和前驅確定父節點
    // 離開時：s.erase(id);
}

// 計算 SG 值
int getSG(int u) {
    int res = 0;
    for (int v : tree[u]) res ^= (getSG(v) + 1);
    return res;
}

int main() {
    // 讀入、構建森林、計算所有根的 SG 異或和
    // 輸出 Alice 或 Bob
}

複雜度

• 事件排序：O(n log n)
• 掃描線每個事件 set 操作：O(log n)
• SG 計算：O(n)
• 總計：O(n log n)，完美通過。

總結

本題融合了三大知識點：

1. 幾何包含關系 → 森林（掃描線構建）
2. 刪除子樹遊戲 → SG 函數（組合遊戲論）
3. 森林 SG 異或和 → 勝負判定（Sprague-Grundy 定理）

是「計算幾何 + 遊戲理論 + 數據結構」的綜合性經典題目。