USACO/namenum

这是USACO Chapter 1 .2中的OI题目Name That Number的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

分析

一个数字对应3个字母，如果我们先枚举出数字所代表的所有字符串，就有3^12种，然后再在5000的字典里寻找，可以用二分查找，数据规模是3^12*log5000=6.5e6，空间规模是5000。

其实可以做的更好！

一个字母只对应一个数字，从字典中读入一个单词，把它转化成唯一对应的数字，看它是否与给出的数字匹配，时间规模是5000*12=6e4，空间规模是常数，而且编程复杂度较低

还可以先比较字符长度和数字长度，如果相等，逐位比较。

     把字母对应成数字我给出个公式，证明不写了，很容易想明白：temp:=ord(nam[i][j])-64;if temp>17 then dec(temp);
num[i]:=num[i]*10+((temp-1) div 3)+2;temp是第i个名字的第j个字符ASCII码-64后的值，num[i]是地i个名字转换成的数字。----by TonyShaw.

【因为之前的temp-1，Z被分到10组，而Q则到了7组。这样似乎还有些问题，如果出现了SUE、QUE，输入783的话，就会出错。不过dict.txt中没有QUE，这种方法对于此题的数据是可行的】

还有一个方法

利用哈希表，把那个字典进行哈希. 然后对于新产生的字符串，在哈希表里进行查找，找到了则加入输出列表. 最后则快排后输出.

补充一下： 可以用集合来处理 s[2]=['A','B','C']; s[3]=['D','E','F']; 由于以3为周期，这种集合的建立可以由div 3得到 但注意其中挖掉了'Q'，这可以分两段来建立集合. 具体见PASCAL最后的那个程序中 'procedure init'

另一种思路

如果我们就使用普通的搜索，可以这样优化：设一个有效奶牛名数量统计s，在读字典时， 首先粗略判断字典中的奶牛名是否是我们所要的（如：长度是否和input文件里一样，首字母代表的数字是否与input文件中的数字一样等等。注意input文件中的数字最好读成字符串处理。）如果不合法，s就不加1. 这样最终剪枝之后，每个数据的有效名称不超过200个，算最坏情况，时间复杂度共计O(5000+200)，可以说相当优秀。 具体情况还可以参考参考代码。[PASCAL语言]

参考代码

C

C++

Pascal

Java

引用

[1]