ZeroJudge 解題筆記：c114. 00409 - Excuses, Excuses!

作者：王一哲
日期：2026年3月10日


ZeroJudge 題目連結：c114. 00409 - Excuses, Excuses!

解題想法

我是用集合儲存關鍵字，用串列儲存答案。讀取一行藉口之後，計算這行之中的關鍵字數量，如果數量是新的最大值，將儲存答案的串列清空、只存入這一行；如果數量等於目前的最大值，這一行加入儲存答案的串列之中。

Python 程式碼

使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

import sys

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    ca += 1
    if ca > 1: result.append("\n")
    result.append(f"Excuse Set #{ca:d}\n")
    n, m = map(int, line.split())  # n 個關鍵字，m 行藉口
    keyword = {sys.stdin.readline().strip() for _ in range(n)}  # 關鍵字集合
    worst = []  # 最爛的藉口
    imax = 0  # 最爛的藉口關鍵字數量
    for _ in range(m):  # 讀取 m 行
        excuse = sys.stdin.readline().rstrip()  # 藉口
        cnt = 0  # 這個藉口的關鍵字數量
        word = []  # 暫存字母用的串列
        for c in excuse:  # 依序讀取字元 c
            if c.isalpha():  # 如果 c 是字母
                word.append(c.lower())  # 轉成小寫加入 word
            else:  # 反之，將 word 組成字串，如果是關鍵字，cnt 加 1
                if "".join(word) in keyword: cnt += 1
                word.clear()  # 漬空 word
        if "".join(word) in keyword: cnt += 1  # 最後要再結算一次
        word.clear()  # 漬空 word
        if cnt > imax:  # 如果 cnt 大於 imax
            imax = cnt  # 更新 imax
            worst = [excuse]  # 找到新的最爛藉口
        elif cnt == imax:  # 如果 cnt 等於 imax
            worst.append(excuse)  # 最爛藉口加一
    for s in worst: result.append(f"{s}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 344 kB，通過測試。

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <cctype>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int ca = 0, n, m;
    while(cin >> n >> m) {
        cin.ignore();
        ca++;
        if (ca > 1) cout << "\n";
        cout << "Excuse Set #" << ca << "\n";
        string s;
        set<string> keyword;
        for(int i=0; i<n; i++) {
            getline(cin, s);
            keyword.insert(s);
        }
        int imax = 0;
        vector<string> worst;
        for(int i=0; i<m; i++) {
            getline(cin, s);
            int cnt = 0;
            string word = "";
            for(char c : s) {
                if (isalpha(c)) {
                    c = tolower(c);
                    word += c;
                } else {
                    if (keyword.count(word) == 1) cnt++;
                    word.clear();
                }
            }
            if (keyword.count(word) == 1) cnt++;
            word.clear();
            if (cnt > imax) {
                imax = cnt;
                worst.clear();
                worst.push_back(s);
            } else if (cnt == imax) {
                worst.push_back(s);
            }
        }
        for(auto w : worst) cout << w << "\n";
    }
    return 0;
}