UVALive 7043 International Collegiate Routing Contest 字典樹IPv4補集輸出

問題描述

給定若干 IPv4 子網（如 192.168.1.0/24），求最小的子網集合，使其與輸入集合無交集，且兩者並集為整個 IPv4 地址空間（即輸出補集）。

Trie 樹建模

IPv4 地址 32 位，整個地址空間對應一棵深度 32 的二叉樹。每個子網對應樹上某節點的子樹。
插入所有輸入子網，標記終結節點 val[u] = true。
DFS 遍歷：若當前節點被覆蓋（val[u]），直接返回；否則遞歸子節點。若子節點不存在，說明該分支未被覆蓋，輸出對應子網。

關鍵代碼

struct Trie {
    int ch[maxnode][2]; bool val[maxnode]; int sz;
    void insert(char* s, int len) { ... } // 插入二進制串
    
    void dfs(int u, int dep, ll cur) {
        if (val[u]) return; // 被輸入子網覆蓋
        for (int i = 1; i >= 0; --i) { // 優先較大IP（按題目要求字典序？）
            ll ip = cur | ((ll)i << (31 - dep));
            if (!ch[u][i]) output_subnet(ip, dep);
            else dfs(ch[u][i], dep + 1, ip);
        }
    }
    
    void output_subnet(ll ip, int len) {
        int a[4];
        for (int i = 3; i >= 0; --i) { a[i] = ip % 256; ip >>= 8; }
        printf("%d.%d.%d.%d/%d\n", a[0], a[1], a[2], a[3], len + 1);
    }
};

IP 地址轉換

• 點分十進制 → 32 位整數：((a<<24)|(b<<16)|(c<<8)|d)
• 整數 → 二進制串：高位在前
• 子網 /len 表示前 len 位固定

注意事項

• 輸入可能有重複/包含關係的子網，Trie 插入自動處理
• 輸出子網數可能為 0（輸入覆蓋全空間）或 1（輸入為空，輸出 0.0.0.0/0）
• 節點數上限：n × 32 ≤ 1.6×10⁷，需靜態分配或動態擴展