HDU 1800 Flying to the Mars：字典樹統計最大重複數

題目大意

N (≤ 3000) 名士兵，每人有一個等級號（非負整數，< 10³⁰，即最多 30 位）。高等級可教低等級，每人最多一師一徒。求最少需要多少根魔法掃帚（即最少鏈數），使所有士兵都能練習。等價於：將數列分解為最少條嚴格遞減子序列。由 Dilworth 定理，答案 = 數列中出現次數最多的數的頻率（即最大重複數）。

解法：字典樹計數

等級號長度 ≤ 30，不可用整數類型直接存儲（超 64 位），需按字符串處理。字典樹每個節點存 next[10] 和 cnt。插入時跳過前導 0，到達末尾 cnt++，維護全局最大值。

關鍵代碼

#include 
#include 
#include 

struct Node {
    int cnt;
    Node* next[10];
    Node() : cnt(0) { memset(next, 0, sizeof(next)); }
};

Node* root;
int ans;

void insert(const char* s) {
    Node* p = root;
    for (int i = 0; s[i]; ++i) {
        int d = s[i] - '0';
        if (!p->next[d]) p->next[d] = new Node();
        p = p->next[d];
    }
    p->cnt++;
    if (p->cnt > ans) ans = p->cnt;
}

void destroy(Node* p) {
    if (!p) return;
    for (int i = 0; i < 10; ++i) destroy(p->next[i]);
    delete p;
}

int main() {
    int n;
    char str[35];
    while (~scanf("%d", &n)) {
        root = new Node();
        ans = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%s", str);
            // 跳過前導 0
            int p = 0;
            while (str[p] == '0' && str[p+1]) ++p;
            insert(str + p);
        }
        printf("%d\n", ans);
        destroy(root); // 避免內存洩漏導致 MLE
    }
    return 0;
}

複雜度

• 時間：O(N × L) = 3000 × 30 = 9×10⁴，極快。
• 空間：最多 N×L 節點 ≈ 9×10⁴ 節點，每節點 ~44 bytes，總 ~4 MB。

關鍵點總結

• **等價轉化**：最少嚴格遞減子序列分解數 = 最大重複頻率（Dilworth 定理在全序集上的應用）。
• **大整數處理**：字符串 + 字典樹，跳過前導 0 統一表示。
• **內存管理**：多測試案例必須釋放字典樹，否則累積 MLE。
• **邊界情況**：全 0 號碼（如 "000"）跳過前導 0 後為空串，需至少保留一個 '0'，代碼中 str[p+1] 保證不全刪。

總結

HDU 1800 看似複雜，實則是「求最大重複數」的偽裝。字典樹是處理超長整數計數的標準工具，配合 Dilworth 定理洞見，代碼極短且高效。