斯诺登的密码 - 题目列表

题意

给出一句英文句子。先找出其中所有表示数字的单词，把每个数字平方后对 100 取模，得到若干个两位数。然后重新排列这些两位数，拼出尽可能小的密码。

思路

先用字典保存单词到数字的映射。每遇到一个合法数字单词，就计算：

text

1value * value % 100

题目要求把结果当作两位数，例如 1 要看成 01，4 要看成 04。在 Python 中可以写成：

python

1f"{x:02d}"

因为每一段长度都固定为两位，想让拼接后的整体最小，只需要把这些两位字符串升序排序，再拼起来。最后把整体前导零删除；如果删完为空，就输出 0。

这题不需要枚举排列，排序就是正解。历史目录中保留 C++ 暴力文件，本文不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：普通 dict 适合保存单词到数字的映射。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：parts.sort() 对等长字符串升序排序。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：split() 拆分单词，"".join(...) 拼接答案。
f"{x:02d}" 把整数格式化成至少两位，不足补前导零。

代码

python

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
40
41word_to_number = {
    "zero": 0,
    "one": 1,
    "two": 2,
    "three": 3,
    "four": 4,
    "five": 5,
    "six": 6,
    "seven": 7,
    "eight": 8,
    "nine": 9,
    "ten": 10,
    "eleven": 11,
    "twelve": 12,
    "thirteen": 13,
    "fourteen": 14,
    "fifteen": 15,
    "sixteen": 16,
    "seventeen": 17,
    "eighteen": 18,
    "nineteen": 19,
    "twenty": 20,
    "a": 1,
    "both": 2,
    "another": 1,
    "first": 1,
    "second": 2,
    "third": 3,
}

words = input().strip().rstrip(".").lower().split()
parts = []

for word in words:
    if word in word_to_number:
        value = word_to_number[word]
        parts.append(f"{value * value % 100:02d}")

parts.sort()
password = "".join(parts).lstrip("0")
print(password if password else "0")

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

cpp

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 14:53
 * update_at: 2026-08-14 14:53
 */
#include <iostream>
#include <string>
#include <algorithm>

const int dict_size = 27;
const int max_nums = 10;

int main() {
    // 英文数字单词（正规 + 非正规写法）到数值的一一映射
    const std::string words[dict_size] = {
        "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen",
        "seventeen", "eighteen", "nineteen", "twenty",
        "a", "both", "another", "first", "second", "third"};
    const int values[dict_size] = {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
        10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
        1, 2, 1, 1, 2, 3};

    int nums[max_nums];  // 每个有效单词平方后对 100 取模的值
    int count = 0;

    // 逐词读入，命中单词表才保留该词的平方末两位
    std::string word;
    while (std::cin >> word) {
        for (int i = 0; i < dict_size; i += 1) {
            if (word == words[i]) {
                nums[count] = values[i] * values[i] % 100;
                count += 1;
                break;
            }
        }
    }

    // 每个数都占两位：升序排序后依次拼接，得到的就是最小的排列
    std::sort(nums, nums + count);

    std::string answer = "";
    for (int i = 0; i < count; i += 1) {
        if (nums[i] < 10) {
            answer += '0';
        }
        answer += std::to_string(nums[i]);
    }

    // 去掉开头多余的 0；全部是 0 时说明没有有效数字，输出 0
    int pos = 0;
    while (pos < (int)answer.size() && answer[pos] == '0') {
        pos += 1;
    }
    if (pos == (int)answer.size()) {
        std::cout << 0 << '\n';
    } else {
        std::cout << answer.substr(pos) << '\n';
    }

    return 0;
}

Pythonic 写法

字典映射 + 推导式生成平方末两位后排序拼接：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15word_to_number = {
    "zero": 0, "one": 1, "two": 2, "three": 3, "four": 4, "five": 5,
    "six": 6, "seven": 7, "eight": 8, "nine": 9, "ten": 10, "eleven": 11,
    "twelve": 12, "thirteen": 13, "fourteen": 14, "fifteen": 15, "sixteen": 16,
    "seventeen": 17, "eighteen": 18, "nineteen": 19, "twenty": 20,
    "a": 1, "both": 2, "another": 1, "first": 1, "second": 2, "third": 3,
}

words = input().strip().rstrip(".").lower().split()
parts = sorted(
    f"{word_to_number[w] * word_to_number[w] % 100:02d}"
    for w in words
    if w in word_to_number
)
print("".join(parts).lstrip("0") or "0")

复杂度

句子只有 6 个单词，时间和空间都可视为 $O(1)$ 。若按单词数 m 计，排序复杂度是 $O(m\log m)$ 。

总结

这题表面像全排列，关键观察是每一块都是两位。等长块要拼出最小结果，直接升序排序即可。