POJ 2418 Hardwood Species：字典樹統計樹種占比

題目描述

輸入最多 1,000,000 行樹種名稱（每行一個，長度 ≤ 30，含大小寫字母、空格等任意字符），輸出每個樹種名稱及其佔總數百分比（保留 4 位小數），按字典序排序。

解法一：字典樹（Trie） - 經典做法

由於字符集包含所有可打印字符（ASCII 32~126），需構建 95 叉或 127 叉樹。每個節點記錄 cnt（以此節點結尾的單詞數）。插入時統計總數 tot。中序遍歷（按字符編碼順序）輸出，利用回溯構建字符串。

關鍵代碼

const int MAXN = 127; // 0~126 ASCII
struct Node {
    int cnt;
    Node* ch[MAXN];
    Node() : cnt(0) { memset(ch, 0, sizeof(ch)); }
};

Node* root = new Node();
int tot = 0;

void insert(const char* s) {
    Node* u = root;
    for (int i = 0; s[i]; ++i) {
        int id = s[i];
        if (!u->ch[id]) u->ch[id] = new Node();
        u = u->ch[id];
    }
    u->cnt++;
}

void dfs(Node* u, char* buf, int dep) {
    if (!u) return;
    if (u->cnt) {
        buf[dep] = '\0';
        double pct = (double)u->cnt / tot * 100;
        printf("%s %.4f\n", buf, pct);
    }
    for (int i = 0; i < MAXN; ++i)
        if (u->ch[i]) {
            buf[dep] = i;
            dfs(u->ch[i], buf, dep + 1);
        }
}

int main() {
    char str[40];
    while (gets(str)) {
        if (str[0] == '\0') break;
        insert(str);
        tot++;
    }
    char buf[40];
    dfs(root, buf, 0);
    return 0;
}

解法二：std::map - 簡潔高效

利用 map<string, int> 自動按鍵排序，代碼極短，實測通過（雖較 Trie 慢但足夠）。

#include <iostream>
#include <map>
#include <string>
#include <cstdio>
using namespace std;

int main() {
    map<string, int> mp;
    string str;
    int tot = 0;
    while (getline(cin, str)) {
        mp[str]++;
        tot++;
    }
    for (auto& p : mp) {
        cout << p.first << ' ';
        printf("%.4f\n", (double)p.second / tot * 100);
    }
    return 0;
}

解法三：讀入所有字符串，排序後統計

存入 vector<string>，sort 後線性掃描計數輸出。內存佔用較大但思路簡單。

關鍵點總結

1. 字符集處理：題目非僅字母+空格，需全 ASCII 範圍，Trie 分支因子至少 95。
2. 輸入量大：建議用 scanf/gets 而非 cin，或關閉同步 ios::sync_with_stdio(false)。
3. 輸出格式：百分比保留 4 位小數，%.4f 即可。
4. 空行結束：輸入以空行或 EOF 結束。