[刷题]算法竞赛入门经典(第2版) 4-6/UVa508 - Morse Mismatches

书上具体所有题目:http://pan.baidu.com/s/1hssH0KO

代码:(Accepted,10 ms)

//UVa508 - Morse Mismatches
#include<iostream>
#include<string>
#include<map>
using namespace std;
map<char, string> morse;
map<string, string> word;
string wo, tran, result;
char c; int cmp(string a, string b) {
if (a == b) return 0;
if (a.size() > b.size()) a.swap(b);
if (a == b.substr(0, a.size())) return b.size() - a.size();
return 666;
} int main()
{
//freopen("in.txt", "r", stdin);
//ios::sync_with_stdio(false);
while ((cin >> c) && c != '*') cin >> morse[c];
while ((cin >> wo) && wo[0] != '*') {
auto cp = wo.begin();
tran = morse[*cp];
while (++cp != wo.end())
tran += morse[*cp];
word[wo] = tran;
}
while ((cin >> tran) && tran[0] != '*') {
result.clear();
int min = 888;
for (auto i = word.begin();i != word.end();++i) {
if (i->second == tran)//精确寻找
if (!result.size() || *result.rbegin() == '?') result = i->first;
else { result += "!";break; }
else if (!result.size() || *result.rbegin() == '?') {//模糊寻找
int n = cmp(tran, i->second);
if (n<min) min = n, result = i->first + "?";
}
}
cout << result << '\n';
}
return 0;
}

分析:思路是先根据电报代码表把单词全部转换成代码,单词和其代码存在一个map里,然后一个个检测下面的码的匹配。精确匹配不用说,如果只找到一个,直接输出,找到多个的话还是只输出第一个,但加一个“!”;模糊匹配是检索每个单词的代码,看哪一串缺的最多出来的代码最少

/*

看VJ上好些0ms的,但我又想不出来什么更好的算法。想过会不会是循环的问题,于是试过将精确寻找和模糊寻找分开循环,结果还是10ms。就想到应该又是流的速度太慢导致。就加了一句ios::sync_with_stdio(false);关了stdio同步,果然变0ms了。唉好吧。。不过想了想不必太较真,博客里使用的还是没关同步的版本。

不用map也可以做的,map似乎还自带排序来着?我也是第一次用map,一开始做没用map,后来想试试看map,就改了。不过改成map后好像有些问题,主要是针对char[]字符串,因为char[]不可以用=来赋值,只能用strcpy()函数,而用这个函数给map赋值报错了,编译通不过,捣鼓半天不知道怎么改,就改用string了,慢一点但是方便。

好几天没刷题了,整个人懒洋洋的,脑子使不出劲,这题写了好久。。主要还是那win10那破一周年更新,导致显卡驱动不正常,折腾了好几天,题目落下了。虽然作为一个win10脑残粉,甚至在考虑要不要回win7.

*/

上一篇:vmstat


下一篇:c# – IObservable以无限循环生成结果