您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

ZOJ 3700 Ever Dream：歌詞關鍵詞提取模擬題

編輯：C++ 入門

ZOJ 3700 Ever Dream：歌詞關鍵詞提取模擬題

題目大意

給定歌詞文本，按以下規則提取關鍵詞：

提取所有單詞（僅含字母，不區分大小寫），統計頻率。
按頻率分組，同頻率為一組。
每組選最長單詞；若多個最長，按字典序排序，取倒數第二個（penultimate）。
按頻率從高到低輸出各組關鍵詞，頻率為 1 的組不輸出。

關鍵細節

單詞定義：連續字母序列。撇號 `'` 視為單詞一部分（如 "I'd" 為一個單詞），非字母非撇號字符作為分隔符。
大小寫統一轉小寫。
字典序比較：標準字符串比較。

演算法流程

逐行讀入，字符流掃描提取單詞，map 統計頻率，記錄最大頻率 max_cnt。
從 max_cnt 遞減到 2，對每個頻率 f：
- 遍歷 map，收集頻率為 f 的單詞，找出最大長度 max_len。
- 用 set 存儲所有長度為 max_len 的單詞（自動去重+字典序排序）。
- 若集合大小 = 1，輸出該詞；若 ≥ 2，取倒數第二個（--(--set.end())）。
各關鍵詞用空格分隔，換行結束。

完整代碼

#include 
#include 
#include 
#include 
#include 
using namespace std;

bool is_alpha(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

int main() {
    int T, n; string s;
    cin >> T;
    while (T--) {
        cin >> n; cin.ignore();
        map freq;
        int max_cnt = 0;
        for (int i = 0; i < n; ++i) {
            getline(cin, s);
            if (s.empty()) continue;
            string word;
            for (int j = 0; j < (int)s.size(); ++j) {
                if (!is_alpha(s[j])) {
                    if (s[j] != '\'') { // 撇號不分割
                        if (!word.empty()) {
                            ++freq[word];
                            max_cnt = max(max_cnt, freq[word]);
                            word.clear();
                        }
                    } else word += s[j];
                } else {
                    if (s[j] >= 'A' && s[j] <= 'Z') s[j] += 32;
                    word += s[j];
                }
            }
            if (!word.empty()) {
                ++freq[word];
                max_cnt = max(max_cnt, freq[word]);
            }
        }

        bool first = true;
        for (int f = max_cnt; f >= 2; --f) {
            set cand;
            int max_len = 0;
            for (auto &p : freq) if (p.second == f) {
                if ((int)p.first.length() > max_len) {
                    max_len = p.first.length();
                    cand.clear(); cand.insert(p.first);
                } else if ((int)p.first.length() == max_len) {
                    cand.insert(p.first);
                }
            }
            if (cand.empty()) continue;
            string out;
            if (cand.size() == 1) out = *cand.begin();
            else {
                auto it = cand.end(); --it; --it; // 倒數第二
                out = *it;
            }
            if (!first) cout << ' ';
            cout << out;
            first = false;
        }
        cout << '\n';
    }
    return 0;
}