10789 Prime Frequency

題目連結

題目敘述

給定一個只包含英數字元（0-9, A-Z, a-z）的字串，你需要計算所有字元的出現頻率（也就是每個字元出現的次數），並只輸出出現頻率是質數的那些字元。

質數是指只能被 1 和它本身整除的整數，例如：2、3、5、7、11 等等。

輸入格式

• 第一行是一個整數 T，代表測資的組數，0 < T < 201

• 接下來的 T 行，每行是一個字串，只包含英數字元，長度為正整數且小於2001

輸出格式

對於每組輸入，輸出一行結果。 這一行應該包含輸出的序號，接著列出那些在輸入字串中出現次數為質數的字元。 這些字元要按照字典序遞增順序排列（即依 ASCII 值從小到大排序）。 詳細格式請參考範例輸入與輸出的對應結果。 如果沒有任何字元的出現頻率是質數，則應輸出 empty。

解題思路

建立一個長度小於 2001 的質數表，用 dict 紀錄字元出現的次數，keys 紀錄字元 ASCII 順序，遍歷 keys 如果 dict[keys] 是質數(prime[dict[keys]] == true)，將字元加入 ans，最後若 ans 為空 ans = "empty"

程式碼

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

int main() {
    vector<bool> prime(2001, true);
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= 2000; i++) {
        if (prime[i]) {
            for (int j = 2; i * j <= 2000; j++){
                prime[i * j] = false;
            }
        }
    }
    int t;
    string s, ans;
    map<char, int> dict;
    vector<char> keys;
    cin >> t;
    for (int i = 0; i < t; i++) {
        ans = "";
        dict.clear();
        keys.clear();
        cin >> s;
        for (char c:s){
            if (dict.find(c) != dict.end()) {
                dict[c]++;
            }else {
                dict[c] = 1;
                keys.push_back(c);
            }
        }
        sort(keys.begin(), keys.end());
        cout << "Case " << i+1 << ": ";
        for (int j = 0; j < keys.size(); j++){
            if (prime[dict[keys[j]]]) {
                ans += keys[j];
            }
        }
        if (ans == "") {
            ans = "empty";
        }
        cout << ans << "\n";
    }
}