題目鏈接:http://ace.delos.com/usacoprob2?a=RqgnadOgSCH&S=namenum題意很簡(jiǎn)單，就是把數(shù)字串轉(zhuǎn)換成可能的字母串。
由于字典很小(<5000)，字母串到數(shù)字串的映射是唯一的，反過(guò)來(lái)算很簡(jiǎn)單。
如果用回溯法算數(shù)字串到字母串的映射再在字典中折半查找，時(shí)間復(fù)雜度為O(3^12*log(5000))，肯定會(huì)超時(shí)。
代碼如下：
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("namenum.in");
ofstream fout("namenum.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
//將字母映射到數(shù)字,不存在的為-1
int map[] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,-1,7,7,8,8,8,9,9,9,-1};
void solve()
{
string object;
in>>object;
int len;
len = object.size();
fstream dict_in("dict.txt");
vector<string> dict;
string temp;
while( dict_in>>temp ){
if(temp.size()==len){
//只取等于數(shù)字串相等的字符串
dict.push_back(temp);
}
}
//sort(dict.begin(),dict.end());
//dict.txt文件已經(jīng)排好序，無(wú)需排序了.
bool find = false;
bool has_result = false;
for(int i=0;i<dict.size();++i){
find = true;
for(int j=0;j<len;++j){
if(map[dict[i][j]-'A']!=object[j]-'0'){
find = false;
break;
}
}
if(find){
out<<dict[i]<<endl;
has_result = true;
}
}
if(!has_result)
out<<"NONE"<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}