【深基6.习5】斯诺登的密码

解题思路

建立数字单词映射，另把 a、another、first 映射 1，both、second 映射 2，third 映射 3。找到单词后计算平方模 100，按升序排列成两位数串，最后去掉总串前导零。

正确性说明

所有块长度均为两位，按数值升序即按块字典序升序，能使拼接串最小；去掉前导零不改变数值。

易错点

zero 不在题目数字表内；twenty 平方模 100 是 0，也要保留其块参与排列；没有数字或全零输出 0。

复杂度

单词数 w，时间 O(w log w)，空间 O(w)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string words[] = {"one",     "two",       "three",    "four",     "five",
                      "six",     "seven",     "eight",    "nine",     "ten",
                      "eleven",  "twelve",    "thirteen", "fourteen", "fifteen",
                      "sixteen", "seventeen", "eighteen", "nineteen", "twenty"};
    map<string, int> m;
    for (int i = 0; i < 20; i++)
        m[words[i]] = i + 1;
    m["a"] = m["another"] = m["first"] = 1;
    m["both"] = m["second"] = 2;
    m["third"] = 3;
    vector<int> v;
    string s;
    while (cin >> s) {
        if (s == ".")
            break;
        if (!s.empty() && s.back() == '.')
            s.pop_back();
        auto it = m.find(s);
        if (it != m.end())
            v.push_back(it->second * it->second % 100);
    }
    sort(v.begin(), v.end());
    string ans;
    for (int x : v) {
        ans += char('0' + x / 10);
        ans += char('0' + x % 10);
    }
    size_t p = ans.find_first_not_of('0');
    cout << (p == string::npos ? "0" : ans.substr(p)) << "\n";
    return 0;
}