ZeroJudge 解題筆記：p919.社團 (Club)

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


ZeroJudge 題目連結：p919.社團 (Club)

解題想法

每組測資第一列為兩個整數 $n$、$m$，分別代表有 $n$ 個人、$m$ 個社團。接下來 $m$ 列，每列一個字串，代表社團的名稱。最後 $n$ 列，每列有 $3$ 個用空格分隔的字串，代表這個人選擇的 $3$ 個社團名稱，社團名稱可能重複，如果重複只會算 $1$ 個人次。題目要統計每個社團各有幾個人填入選社志願。答案要輸出 $m$ 列，按照測資給的社團名稱輸出，每列為社團名稱、人數，中間用空格分隔。

這個題目很適合用字典計數，可以用 Python 的 dict 或是 defaultdict 以及 C++ 的 map 或是 unordered_map 處理。不過用 C++ 解題時，需要再另外開一個 vector 記錄社團名稱順序，用來組合輸出的答案。

由於這題原來只放了無法開啟的題目 pdf 雲端硬碟連結，我一開始無法確定每個人可選的社團數量，所有我有寫另一種可選社團數量不固定的版本，一樣可以 AC，但是寫起來比較複雜。

Python 程式碼

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

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個人
        m = int(data[ptr + 1])  # m 個社團
        ptr += 2
        
        # 用字典儲存各社團人數，先設定 key 值
        cnt = dict()
        for _ in range(m):
            s = data[ptr]
            ptr += 1
            cnt[s] = 0

        # 讀取 n 個人選擇的社團
        for _ in range(n):
            clubs = set(data[ptr : ptr + 3])  # 去除重複的項目
            ptr += 3
            for club in clubs:
                cnt[club] += 1

        # 組合答案
        for k, v in cnt.items():
            result.append(f"{k} {v:d}\n")
    
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

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

while True:
    try:
        n, m = map(int, input().split())  # n 個人，m 個社團
    except EOFError:
        break

    # 用字典儲存各社團人數，先設定 key 值
    cnt = dict()
    for _ in range(m):
        s = input()
        cnt[s] = 0

    # 讀取 n 個人選擇的社團
    for _ in range(n):
        clubs = set(input().split())  # 排除重複的項目
        for club in clubs:
            cnt[club] += 1

    # 組合答案
    for k, v in cnt.items():
        print(f"{k} {v:d}")

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;  // n 個人，m 個社團
    while(cin >> n >> m) {
        // 讀取測資
        vector<string> clubs;
        for(int i = 0; i < m; i++) {
            string s;
            cin >> s;
            clubs.push_back(s);
        }
        
        // 讀取 n 個人的資料
        unordered_map<string, int> cnt;  // 各社團人數
        for(int i = 0; i < n; i++) {
            unordered_map<string, bool> used;  // 社團是否重複
            for(int j = 0; j < 3; j++) {
                string s;
                cin >> s;
                if (!used[s]) {
                    used[s] = true;
                    cnt[s]++;
                }
            }
        }

        // 組合答案
        for(auto club : clubs) {
            cout << club << " " << cnt[club] << "\n";
        }
    }
    return 0;
}

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

#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;  // n 個人，m 個社團
    while(cin >> n >> m) {
        // 讀取測資
        vector<string> clubs;
        for(int i = 0; i < m; i++) {
            string s;
            cin >> s;
            clubs.push_back(s);
        }
        
        // 讀取 n 個人的資料
        cin.ignore();  // 跳過社團名單最後一行的 \n
        unordered_map<string, int> cnt;  // 各社團人數
        for(int i = 0; i < n; i++) {
            unordered_map<string, bool> used;  // 社團是否重複
            string s;
            getline(cin, s);
            stringstream ss (s);
            while(ss >> s) {
                if (!used[s]) {
                    used[s] = true;
                    cnt[s]++;
                }
            }
        }

        // 組合答案
        for(auto club : clubs) {
            cout << club << " " << cnt[club] << "\n";
        }
    }
    return 0;
}