首页 > 代码库 > 【USACO 1.2】Name That Number
【USACO 1.2】Name That Number
给你一串数字（≤12个），每个数字可以对应3个字母，求生成的所有字符串里，在字典内的有哪些。
我做的时候想的是字典树（Trie 树），模拟数串生成的所有字符串，然后在字典树里查找一下。
/*TASK:namenumLANG:C++*/#include <iostream>#include <fstream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long long#define MAX 26#define N 5001#define M 15using namespace std;int top,trie[N*M][MAX+1];int search(char s[]){ int i,rt; for(rt=0,i=0;rt=trie[rt][s[i]-‘A‘];) if(!s[++i])return trie[rt][MAX]; return 0;}void insert(char s[]){ int rt=0; for(int i=0;s[i];i++){ int &nxt=trie[rt][s[i]-‘A‘]; if(0==nxt) nxt=++top; rt=nxt; } trie[rt][MAX]=1;}int cnt;//虽然只有3个字母，但是后面有\0，故要开到4。char ma[12][4]={"","","ABC","DEF","GHI","JKL","MNO","PRS","TUV","WXY"};char s[M],name[M];int dfs(int d){ if(!s[d]){ if(search(name)){ cout<<name<<endl; return 1; } return 0; } int ok=0; for(int i=0;i<3;i++){ name[d]=ma[s[d]-‘0‘][i]; if(dfs(d+1))ok=1; } return ok;}int main() { //freopen("namenum.in","r",stdin); //freopen("namenum.out","w",stdout); ifstream in("dict.txt"); while(in>>s)insert(s); cin>>s; if(!dfs(0))cout<<"NONE"<<endl; return 0;}官方题解里说可以二分，还可以把字典全部转为数字，总共就5000个，这就是逆向思维。
/*TASK:namenumLANG:C++*/#include <iostream>#include <fstream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long long#define MAX 26#define N 5001#define M 15using namespace std;char dic[N][M];int ma[MAX]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9};ll num[N],tot,t;int main() { freopen("namenum.in","r",stdin); freopen("namenum.out","w",stdout); ifstream in("dict.txt"); while(in>>dic[tot]){ ll &ans=num[tot]; for(int i=0;dic[tot][i];i++) ans=ans*10+ma[dic[tot][i]-‘A‘]; tot++; } cin>>t; int ok=0; for(int i=0;i<tot;i++) if(num[i]==t){ok=1;cout<<dic[i]<<endl;} if(!ok)cout<<"NONE"<<endl; return 0;}
【USACO 1.2】Name That Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。