NYOJ 285 尋找克隆人：Map 計數 DNA 序列頻率

問題描述

給 n (≤20000) 個 DNA 序列（長度 ≤20），求每個序列在輸入中出現的次數，輸出「出現 i 次的序列有多少個」對應每行。即：統計頻率的頻率。
輸入以 0 0 結束。

算法

1. 用 unordered_map 統計每個序列出現次數 freq[s]。
2. 用數組 cnt[f] 統計出現 f 次的序列有多少種。遍歷 map：cnt[freq[s]]++。
3. 輸出 cnt[1] 到 cnt[n]（每行一個）。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m, n || m) {
        unordered_map freq;
        string s;
        for (int i = 0; i < n; ++i) {
            cin >> s;
            freq[s]++;
        }
        vector cnt(n+1, 0);
        for (auto& [seq, f] : freq) cnt[f]++;
        for (int i = 1; i <= n; ++i) cout << cnt[i] << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n × 平均長度) ≈ 20000 × 20 = 4e5 字符操作，極快。
• 空間：O(n) 存 map。

關鍵點

• 「頻率的頻率」雙層統計：先序列→次數，再次數→種類數。
• 序列長度 ≤20，直接用 string 作 key，無需哈希優化。
• 輸出 n 行，缺失的次數輸出 0。

簡單哈希表應用，代碼極短，體現「Map 計數」核心模式。