斯诺登的密码

洛谷·深入浅出 · 代码 · cpp · 难度 3/5 · 共 1717 字
把英文数字平方取模后拼成最小数
洛谷
练习
正文

// 原题：https://oj.yecheng.tv/p/1425
// 题意：一句含 6 个单词的话，找出其中用英语表示的数字（<=20），平方后对 100 取模得到两位串，
//       把这些两位串全排列拼成一个数（去前导 0），求能拼出的最小值，没有数字则输出 0。
// 思路：建单词->数值映射；扫描单词收集两位串；next_permutation 枚举所有排列，取拼接去前导 0 后的最小值。
// 复杂度：O(6! * L)，很小。
// 易错点：每个数字先平方再 %100 成两位；排列的是“两位块”而不是单个数字；要去前导 0 再比较。
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main(){
    map<string, int> m;
    m["one"]=1; m["two"]=2; m["three"]=3; m["four"]=4; m["five"]=5; m["six"]=6;
    m["seven"]=7; m["eight"]=8; m["nine"]=9; m["ten"]=10; m["eleven"]=11; m["twelve"]=12;
    m["thirteen"]=13; m["fourteen"]=14; m["fifteen"]=15; m["sixteen"]=16;
    m["seventeen"]=17; m["eighteen"]=18; m["nineteen"]=19; m["twenty"]=20;
    m["a"]=1; m["both"]=2; m["another"]=1; m["first"]=1; m["second"]=2; m["third"]=3;
    vector<string> nums;
    string w;
    while(cin >> w){
        if(!w.empty() && w.back() == '.') w.pop_back();
        for(char &c : w) c = tolower(c);
        if(m.count(w)){
            int v = m[w];
            v = v * v % 100;
            char buf[8];
            snprintf(buf, sizeof(buf), "%02d", v);
            nums.push_back(string(buf));
        }
    }
    if(nums.empty()){ cout << 0 << endl; return 0; }
    sort(nums.begin(), nums.end());
    long long ans = -1;
    do {
        string cat;
        for(auto &x : nums) cat += x;
        int p = 0;
        while(p + 1 < cat.size() && cat[p] == '0') p++;
        string t = cat.substr(p);
        long long val = 0;
        for(char c : t) val = val * 10 + (c - '0');
        if(ans == -1 || val < ans) ans = val;
    } while(next_permutation(nums.begin(), nums.end()));
    cout << ans << endl;
    return 0;
}
斯诺登的密码

正文

洛谷·深入浅出的其它内容
