🔗 UVA-10008 What’s Cryptanalysis?

tags: CPE49 CPE-241015 CPE-110927 雜湊表(Hash Table) 排序(Sorting)

題意

密碼分析是破解他人加密文本的過程，有時涉及對一段（加密的）文本進行統計分析。你的任務是撰寫一個程式來對給定的文本進行簡單的分析。

給定一個正整數 nn ，表示接下來有 nn 行需要分析的文本。接下來的 nn 行中可能包含任意字元（包括空白字元）。這是需要分析的文本。

你需要統計每個字母（不區分大小寫）在文本中出現的次數，並按出現次數的降序排列。如果兩個字母出現的次數相同，則按字母的字母順序排列。沒有出現的字母不應出現在輸出中。

最後輸出時，每個字母及其出現次數佔一行，字母和次數之間用一個空格隔開，且字母需要轉換為大寫。

LuckyCat 的中文翻譯

思路：雜湊表(Hash Table) + 排序(Sorting)

根據題意，我們需要統計每個字母在文本中出現的次數，因此我們可以使用 雜湊表(Hash Table) 來統計每個字母出現的次數，並針對雜湊表的 key 和 value 進行 排序(Sorting) 。

在排序時，我們需要先以字母出現的次數進行排序，如果次數相同，則以字母的字母順序進行排序。

  • 在 Python 中，我們可以使用 sorted() 函數配合 lambda 表達式來實現這個排序。
  • 在 C++ 中，我們可以定義一個比較函數 cmp，並使用 std::sort 來排序。

由於字母的數量只有 2626 個，因此也可以使用陣列來統計每個字母出現的次數，但在排序時需要連同對應的下標一起排序。

複雜度分析

  • 時間複雜度：O(S+Σlog⁡Σ)\mathcal{O}(S + \Sigma \log \Sigma)，其中 SS 是所有文本中字元的總數，Σ\Sigma 是字母的數量，本題中 Σ=26\Sigma = 26。
    • 遍歷所有字元，對每個字元進行檢查和更新操作，時間複雜度為 O(S)\mathcal{O}(S)。
    • 將 Σ\Sigma 個出現過的字母進行排序，時間複雜度為 O(Σlog⁡Σ)\mathcal{O}(\Sigma \log \Sigma)。由於 Σ\Sigma 最多為 2626，因此排序的時間複雜度實際上是常數級的。
  • 空間複雜度：O(Σ)\mathcal{O}(\Sigma)。
    • 需要額外的雜湊表來統計每個字母出現的次數。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import defaultdict

n = int(input())

cnt = defaultdict(int)

for _ in range(n):
    line = input()
    for ch in line:
        if ch.isalpha():
            cnt[ch.upper()] += 1

for k, v in sorted(cnt.items(), key = lambda x : (-x[1], x[0])):
    print(k, v)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

bool cmp(pair<char, int> a, pair<char, int> b) {
    if (a.second == b.second) {
        return a.first < b.first;
    }
    return a.second > b.second;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t;
    string s;
    
    cin >> t;
    unordered_map<char, int> cnt;
    getline(cin, s); // ignore the rest of the line

    while (t--) {
        getline(cin, s);
        for (char ch : s) {
            if (isalpha(ch)) {
                cnt[toupper(ch)]++;
            }
        }
    }
    // Convert map to a vector of pairs for sorting
    vector<pair<char, int>> cntVec(cnt.begin(), cnt.end());

    // Sort the vector based on the frequency and then alphabetically
    sort(cntVec.begin(), cntVec.end(), cmp);

    for (const auto &kv : cntVec) {
        cout << kv.first << " " << kv.second << endl;
    }
    return 0;
}

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), Frieren, frieren, long hair, very long hair, (green eyes:1.5), grey hair, pointy ears, elf,

dress, white dress, sleeveless, sleeveless dress, jewelry, earrings, bare shoulders, parted bangs, bare arms, barefoot, bare legs, collarbone, looking at viewer, blush, sitting, closed mouth, full body, flower, water, wariza, strap slip, between legs, hand between legs, lily pad,

anime girl, sitting in water, white dress, pointed ears, floating flowers, serene, fantasy, soft lighting, dreamy atmosphere,

至少這次 CPE 還是沒有取消必考 49 題的。