Description
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.Input
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.Output
Sample Input
dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay
Sample Output
cat eh loops
咋看是字典树，但是我在搜二分专题的时候看到的这道题，那么这道题肯定能用二分解决
思路很好想，运用到了sscanf函数
#include#include #include using namespace std; struct node { char s1[20],s2[20]; } a[100005]; int len; int cmp(node a,node b) { return strcmp(a.s2,b.s2)<0; } int main() { len = 0; int i,j; char str[50]; while(gets(str)) { if(str[0] == '\0') break; sscanf(str,"%s%s",a[len].s1,a[len].s2); len++; } sort(a,a+len,cmp); while(gets(str)) { int l = 0,r= len-1,mid,flag = 1; while(l<=r) { int mid = (l+r)>>1; if(strcmp(str,a[mid].s2)==0) { printf("%s\n",a[mid].s1); flag = 0; break; } else if(strcmp(str,a[mid].s2)<0) r = mid-1; else l = mid+1; } if(flag) printf("eh\n"); } return 0; }