Sicily 1194：Message Flood - 集合去重統計未讀消息

問題描述

有 n 條已讀消息，m 條新到達消息（不區分大小寫）。求未讀消息條數（即在已讀集合中但不在新到達集合中的消息數）。

解法：Set 去重 + 大小寫轉換

1. 讀入 n, m。
2. 將 n 條消息轉小寫存入 set。
3. 讀入 m 條新消息，轉小寫後若在 set 中則刪除。
4. 輸出 set 剩餘大小。

參考代碼 (C++)

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

int main() {
    int n, m;
    while (cin >> n && n) {
        cin >> m;
        set read;
        for (int i = 0; i < n; ++i) {
            string s; cin >> s;
            for (char &c : s) c = tolower(c);
            read.insert(s);
        }
        for (int i = 0; i < m; ++i) {
            string s; cin >> s;
            for (char &c : s) c = tolower(c);
            if (read.count(s)) read.erase(s);
        }
        cout << read.size() << endl;
    }
    return 0;
}

複雜度

• 時間：O((n+m) × L log n)，L 為平均字符串長度。
• 空間：O(n × L)。

關鍵點

• 不區分大小寫：統一轉小寫（或大寫）處理。
• set 自動去重，直接支持查找/刪除 O(log n)。
• 輸入以 n=0 結束。