UVaOJ 508 - Morse Mismatches

问题描述

解法一：模拟

这题最繁琐的事情反而是读懂题面：给定一个摩斯电码的编码表 morse 以及固定数量的上下文候选词 context. 要求对给定的多个摩斯电码密文 code 进行精确或近似解码。解码规则为：

如果能精确解码成 context 中的某个明文词 word，则输出 word;
如果能精确解码成 context 中的多个明文词，则按照字典序输出第一个 word 并带上 ! 符号；
如果不能精确解码，则尝试寻找 基于密文 code 做最少数量 . 和 - 改动后 能够精确匹配上的词，带上 ? 符号。

因此我们可以把 context 中的候选词全部用一个 map 存下来， .first （即 key）为明文， .second（即 Value）为摩斯密文。那么题目就变成了在纯粹的密文（摩斯码）形式下的比较，降低了处理难度。对于近似匹配情况，只需要按照 string 默认的字典序扫一遍，如果比较的密文之间存在前缀关系（我用了 find 起始位置为 0 来判断），就说明可以通过在尾部做增删变换得到，找到改动数量 min_diff 最小的第一个明文词就好了。

注：尽管题目描述中对输出有字典序要求，但是测评时（包括 uDebug）只要保证密文是匹配上的就行了。

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ