NEFU 643 Teacher Li：ASCII 碼相減找缺席學生

問題描述

有 n 個學生名單，今日到課 n-1 人，缺 1 人。名字長度不一，僅含可見字符。n ≤ 1000，名字長度 ≤ 30。需找出缺席者名字。

核心洞察：字符頻率差 = 缺席名字

將所有 n 個名字的每個位置字符 ASCII 碼加總，再減去 n-1 個到課名字對應位置的 ASCII 碼，剩下的正是缺席名字的字符碼。

原理：同位置字符出現次數相同，唯有缺席者的字符多一次。

演算法步驟

1. 開陣列 sum[32] = {0} 記錄每位置字符碼總和。
2. 讀入 n 個名字，對每個名字每位置 sum[pos] += ch。
3. 讀入 n-1 個名字，對每個名字每位置 sum[pos] -= ch。
4. 從 sum[0] 開始輸出非零字符，直到遇到 0 或超過最大長度。

完整程式碼（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, caseNo = 1;
    while (cin >> n) {
        vector<int> sum(32, 0);
        string name;
        // 讀入 n 個名字
        for (int i = 0; i < n; ++i) {
            cin >> name;
            for (int j = 0; j < (int)name.size(); ++j) sum[j] += name[j];
        }
        // 讀入 n-1 個名字
        for (int i = 0; i < n-1; ++i) {
            cin >> name;
            for (int j = 0; j < (int)name.size(); ++j) sum[j] -= name[j];
        }
        cout << "Scenario #" << caseNo++ << '\n';
        for (int v : sum) {
            if (v == 0) break;
            cout << char(v);
        }
        cout << "\n\n";
    }
    return 0;
}

複雜度分析

• 時間：O(n × L)，L 為平均名字長度（≤ 30）。
• 空間：O(L)，只需 32 個整數。

為什麼 map/set 會超時？

若用 map<string,int> 計數，字符串哈希/比較常數極大；n=1000 時雖理論可行，但常數因子導致 TLE。ASCII 相減法無哈希、無動態分配、極簡運算，絕對快。

測試樣例

輸入：
3
Alice
Bob
Charlie
Alice
Bob

輸出：
Scenario #1
Charlie