大致题意:
输入一个字典,字典格式为“英语à外语”的一一映射关系
然后输入若干个外语单词,输出他们的 英语翻译单词,如果字典中不存在这个单词,则输出“eh”。
。
1、直接使用map。。。。 938MS
#include <string> #include <cstdio> #include <cstring> #include <iostream> #include <cstdlib> #include <map> using namespace std; int main() { char english[11], foreign[11]; map<string, string> translate; // freopen("in.txt","r",stdin); while(true) { char t; if((t=getchar())=='\n') break; else { english[0] = t; int i = 1; while(true) { t = getchar(); if(t == ' ') { english[i] = '\0'; break; } else english[i++] = t; } } scanf("%s",foreign); getchar(); translate[foreign] = english; } char word[11],ans[11]; while(~scanf("%s", word)) { if(translate.find(word)!=translate.end()) { strcpy(ans,translate[word].c_str()); printf("%s\n",ans); } else printf("eh\n"); } return 0; }
2 、排序+二分查找 375MS
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct word { char en[11], fl[11]; bool operator < (const word& rhs) const { return strcmp( fl, rhs.fl)<0; } }; word DICT[100001]; int n; int BinarySrearch(char s[], int n) { int l = 0, r = n-1, mid; while(l<=r) { mid = (l+r) >> 1; if( strcmp(s, DICT[mid].fl) == 0) return mid; else if(strcmp(s, DICT[mid].fl) < 0) r = mid - 1; else l = mid + 1; } return -1; } void init() { char str[30]; n = 0; while(gets(str)) { if(str[0]=='\0') break; sscanf(str,"%s %s", DICT[n].en, DICT[n].fl); n++; } sort(DICT, DICT + n); } void work() { char temp[11]; int key; while(gets(temp)) { key = BinarySrearch(temp, n); if(-1 == key) printf("eh\n"); else printf("%s\n", DICT[key].en); } } int main() { init(); work(); return 0; }
3、字符串hash (拉链法) 188MS
#include <stdio.h> #include <string.h> const int M = 200000; typedef struct word { char e[11]; char f[11]; int next; }; word dict[M]; int n = 1; int Hash[M]; int ELFHash(char* key) { unsigned int h = 0; while(*key) { h = (h<<4) + (*key++); unsigned int g = h&(0xf00000000L); if(g) h^=g>>24; h&=~g; } return h%M; } void find(char f[]) { int h = ELFHash(f); for(int k=Hash[h]; k; k=dict[k].next) { if(strcmp(f, dict[k].f)==0) { printf("%s\n",dict[k].e); return ; } } printf("eh\n"); } int main() { char str[23]; while(gets(str)) { if(str[0]=='\0') break; sscanf(str,"%s %s",dict[n].e,dict[n].f); int h = ELFHash(dict[n].f); dict[n].next = Hash[h]; Hash[h] = n++; } while(gets(str)) { find(str); } return 0; }