问题描述
p508原题链接:UVaOJ 508 - Morse Mismatches
相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-6
解法一:模拟
这题最繁琐的事情反而是读懂题面:给定一个摩斯电码的编码表 morse 以及固定数量的上下文候选词 context. 要求对给定的多个摩斯电码密文 code 进行精确或近似解码。解码规则为:
- 如果能精确解码成 context 中的某个明文词 word,则输出 word;
- 如果能精确解码成 context 中的多个明文词,则按照字典序输出第一个 word 并带上 ! 符号;
- 如果不能精确解码,则尝试寻找 基于密文 code 做最少数量 . 和 - 改动后 能够精确匹配上的词,带上 ? 符号。
因此我们可以把 context 中的候选词全部用一个 map 存下来, .first (即 key)为明文, .second(即 Value) 为摩斯密文。那么题目就变成了在纯粹的密文(摩斯码)形式下的比较,降低了处理难度。对于近似匹配情况,只需要按照 string 默认的字典序扫一遍,如果比较的密文之间存在前缀关系(我用了 find 起始位置为 0 来判断),就说明可以通过在尾部做增删变换得到,找到改动数量 min_diff 最小的第一个明文词就好了。
注:尽管题目描述中对输出有字典序要求,但是测评时(包括 uDebug)只要保证密文是匹配上的就行了。
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 |
#include <bits/stdc++.h> using namespace std; map<char, string> morse; map<string, string> context; string match(string code) { vector<string> res; for (auto word : context) if (code == word.second) res.push_back(word.first); if (res.size() == 1) return res[0]; if (res.size() >= 2) return res[0] + "!"; string appr = context.begin()->first; int min_diff = INT_MAX; for (auto word : context) if (!code.find(word.second) || !word.second.find(code)) if (labs(code.length() - word.second.length()) < min_diff) { appr = word.first; min_diff = labs(code.length() - word.second.length()); } return appr + "?"; } int main() { string code, word; while (cin >> word && word != "*") { cin >> code; morse[word[0]] = code; } while (cin >> word && word != "*") for (auto w : word) context[word] += morse[w]; while (cin >> code && code != "*") cout << match(code) << endl; return 0; } |
1 |
#TODO |