ZeroJudge C044: What’s Cryptanalysis

同題: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
ZeroJudge C044 範例測資

解題思路

先使用一個 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

發佈留言