poj2503-Babelfish
这个题我是用字典树写的，也可以用map实现，字典树可学习这篇博客
传送门：https://blog.csdn.net/weixin_39778570/article/details/81990417
题意：
每行输入两个单词，可以通过右边的单词查到左边的单词，这样形成一本字典；输入一个空行，然后开始输入要查询的单词，找到它在字典上对应的单词；
题解：
形成字典用字典树实现，将要查询的单词建树，将最后一个数字存入数组标记上翻译后的单词；输入空行开始查询可以用gets() 实现，读入字符串然后判断长度是否为0；
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 7 char a[100]; 8 char b[100],c[100]; 9 char s[400010][20]; 10 int tree[400010][30]; 11 int color[400010]; 12 int tot=1; 13 14 void insert() 15 { 16 int len=strlen(c); 17 int p=0; 18 for(int i=0;i<len;i++){ 19 int k=c[i]-'a'; 20 if(!tree[p][k]){ 21 tree[p][k]=tot; 22 tot++; 23 } 24 p=tree[p][k]; 25 } 26 color[p]=1; 27 strcpy(s[p],b); 28 } 29 30 void query() 31 { 32 int p=0; 33 int len=strlen(a); 34 for(int i=0;i<len;i++){ 35 int k=a[i]-'a'; 36 if(!tree[p][k]){ 37 printf("eh\n"); 38 return; 39 } 40 p=tree[p][k]; 41 } 42 if(!color[p]) printf("eh\n"); 43 else printf("%s\n",s[p]); 44 } 45 46 int main() 47 { 48 while(gets(a)) { 49 int len=strlen(a); 50 if(len==0) break; 51 int flag=1,k=0; 52 for(int i=0;i<len;i++){ 53 if(a[i]==' '){ 54 k=0; 55 flag=0; 56 continue; 57 } 58 if(flag) b[k++]=a[i]; 59 else c[k++]=a[i]; 60 } 61 insert(); 62 } 63 while(gets(a)){ 64 if(strlen(a)==0) break; 65 query(); 66 } 67 return 0; 68 }
查看16道真题和解析
