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";
  }
}