同題:UVa 10008 – What’s Cryptanalysis
密碼翻譯 (Cryptanalysis) 是指把某個人寫的密文 (Cryptographic Writing) 加以分解。這個程序通常會對密文訊息做統計分析。你的任務就是寫一個程式來對密文作簡單的分析。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入的第 1 列有一個正整數 N,代表以下有多少列需要作分析的密文。 接下來的 N 列,每列含有 0 或多個字元 (可能包含空白字元)。 | 每列包含一個大寫字元 (A~Z) 和一個正整數。這個正整數代表該字元在輸入中出現的次數。輸入中大小寫 (例如:A 及 a) 視為相同的字元。輸出時請按照字元出現的次數由大到小排列,如果有2個以上的字元出現次數相同的話,則按照字元的大小 (例如:A 在 H 之前) 由小到大排列。 請注意:如果某一字元未出現在輸入中,那他也不應出現在輸出中。 |
3 This is a test. Count me 1 2 3 4 5. Wow!!!! Is this question easy? | S 7 T 6 I 5 E 4 O 3 A 2 H 2 N 2 U 2 W 2 C 1 M 1 Q 1 Y 1 |
解題思路
先使用一個 Map 來存取每一個字元出現的次數,可以使用 isalpha 來判斷目前字元是否為英文字母,並使用toupper來將英文字母轉換成大寫的型態做 Map 的 Key。
再來使用 for (auto it:Map),並且再宣告一個新的 Map (Key: int|Value: Vector),這個新的 Map 是存有哪些字元出現在同一個次數上。因為題目要求要由大排到小,所以將次數乘以-1並將其字元Push_Back到新的Map中。
輸出時也是用 Auto 跑新 Map 的迴圈,先將新的 Map 的 Vector 進行排序,然後再跑一個新的 Map 中 Vector 的 For迴圈,將裡面的字元和目前Key乘以-1 (剛剛乘以-1現在要復原) 進行輸出。
範例程式碼-ZeroJudge C044: What’s Cryptanalysis
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
pair<int, char> rtn (int a, char b)
{
pair<int, char>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
string a;
getline(cin, a);
map<char, int>MAP;
for (int i = 0; i<N; i++)
{
string str;
getline(cin, str);
for (int j = 0; j<str.length(); j++)
{
if (isalpha(str[j])) MAP[toupper(str[j])]++;
}
}
map<int, vector<char>>ans;
for (auto it:MAP)
{
ans[it.second * -1].push_back(it.first);
}
for (auto it:ans)
{
vector<char>result = it.second;
int num = it.first * -1;
sort(result.begin(), result.end());
for (int i = 0; i<result.size(); i++)
{
cout << result[i] << " " << num << "\n";
}
}
}
//ZeroJudge C044
//Dr. SeanXD