大意：给定n(n<=100000)对外文 英文单词 ，给出外文单词求英文单词。
分析：枚举超时用二分。
代码：
#include#include #include #include const int maxn = 100010;using namespace std;struct node{ char e[60], s[60];}dic[maxn];char t[60];int pos;int cmp(node a, node b){ return strcmp(a.s, b.s) < 0;}int binserch(char *s){ int l = 0, r = pos - 1; while (l <= r) { int mid = (l + r) / 2; if (strcmp(dic[mid].s, s) == 0) return mid; else if (strcmp(dic[mid].s, s) > 0) r = mid - 1; else l = mid + 1; } return -1;}int main(){ //freopen("C:\\in.txt", "r", stdin); pos = 0; char z; while (scanf("%s%c", dic[pos].e, &z) != EOF) { if (z == '\n') { strcpy(t, dic[pos].e); break; } scanf("%s", dic[pos++].s); } sort(dic, dic + pos, cmp); int num = binserch(t); if (num >= 0) printf("%s\n", dic[num].e); else printf("eh\n"); while (scanf("%s", t) != EOF) { num = binserch(t); if (num >= 0) printf("%s\n", dic[num].e); else printf("eh\n"); } return 0;}
hash解决：
#include#include #include const int mm = 100003;using namespace std;struct NODE{ char english[12]; char qlish[12];}dict[mm];int hashn[mm], nextn[mm];int ELFhash(char *key)//字符串hash{ long long h = 0; long long g; while (*key) { h = (h << 4) + *key++; g = h & 0xf0000000L; if (g) h^= g >> 24; h &= ~g; } return h%mm;}int main(){ //freopen("C:\\in.txt", "r", stdin); char ss[30]; int n = 0; memset(hashn, -1, sizeof(hashn)); while (gets(ss)) { if (sscanf(ss,"%s%s",dict[n].english, dict[n].qlish) != 2)//sscanf从字符串中读进与指定格式相符的数据。 break; else { int key = ELFhash(dict[n].qlish);//拉链法解决冲突，模拟链表。 nextn[n] = hashn[key]; hashn[key] = n; n++; } } while (~scanf("%s", ss)) { int i = hashn[ELFhash(ss)]; while (i != -1) { if (!strcmp(dict[i].qlish, ss)) break; i = nextn[i]; } if (i == -1) printf("eh\n"); else printf("%s\n", dict[i].english); } return 0;}