题意还是很简单的，我们可以用dfs穷举出所有可能的名字；重要的是查询名字是不是合法，，开始的时候用的map，没想到超时了；于是后面用的字典树，其实应该也可以用二分进行查找。另外好像USACO对内存限制很严，数组不能开太大。
代码如下：
/*ID: 15674811LANG: C++TASK: namenum*/using namespace std;ofstream fout(“namenum.out”);ifstream fin(“namenum.in”);//ifstream fin(“lkl.txt”);typedef struct{int ch[26];int flag;}N;N node[50000];int top;void Insert(char *str){int len=strlen(str);int t=0;for(int i=0;i<len;i++){if(node[t].ch[str[i]-‘A’]==0)node[t].ch[str[i]-‘A’]=++top;t=node[t].ch[str[i]-‘A’];}node[t].flag=1;}int query(char *str){int len=strlen(str);int t=0;for(int i=0;i<len;i++){if(node[t].ch[str[i]-‘A’]==0)return 0;t=node[t].ch[str[i]-‘A’];}if(node[t].flag)return 1;return 0;}int flag;char str[20];char tmp[20][10];char ans[20];int len;void dfs(int cnt){if(cnt==len){ans[cnt]=’\0′;if(query(ans)){fout<<ans<<endl;flag=1;}return ;}for(int i=1;i<=3;i++){ans[cnt]=tmp[str[cnt]-‘0′][i];dfs(cnt+1);}}int main(){int k=0;for(int i=2;i<=9;i++)for(int j=1;j<=3;j++){tmp[i][j]=’A’+k;if(tmp[i][j]==’Q’)tmp[i][j]=’A’+(++k);k++;}memset(node,0,sizeof(node));top=0;ifstream fin1(“dict.txt”);while(fin1>>str){Insert(str);}while(fin>>str){flag=0;len=strlen(str);dfs(0);if(flag==0)fout<<“NONE”<<endl;} return 0;}
以后我会去到很多很繁华或苍凉，
