Problem C: Babelfish

Problem C: Babelfish

时间: 1ms        内存:128M

描述:

Problem C: Babelfish

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 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 is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".

输入:

输出:

示例输入:

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

示例输出:

cat
eh
loops

提示:

参考答案(内存最优[3992]):

#include <cstdio>
#include <cstring>
const int maxn=100000+10;
const int maxs=10+5;
char dict[maxn][2][maxs];
int n;
bool isblank(char s[])
{
    int k=strlen(s);
    while(--k>=0)
        if(s[k]>='a'&&s[k]<='z')
        return false;
    return true;
}
void swap(char a[],char b[])
{
    char t[maxs];
    strcpy(t,a);
    strcpy(a,b);
    strcpy(b,t);
}
void sort(int a,int b,char s[][2][maxs])
{
    if(a>=b)
        return;
    char t[maxs];
    strcpy(t,s[(a+b)/2][1]);
    int i,j;
    i=a-1,j=b+1;
    do
    {
        do
            ++i;
        while(strcmp(t,s[i][1])>0);
        do
            --j;
        while(strcmp(t,s[j][1])<0);
        if(i<j)
        {
            swap(s[i][0],s[j][0]);
            swap(s[i][1],s[j][1]);
        }
    }while(i<j);
    sort(a,j,s);
    sort(j+1,b,s);
}
int find(char s[])
{
    int l,r;
    l=0;
    r=n;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(strcmp(dict[mid][1],s)<=0)
            l=mid;
        else
            r=mid;
    }
    if(strcmp(dict[l][1],s))
        return -1;
    return l;
}
int main()
{
    char s[maxs+maxn];
    n=0;
    gets(s);
    while(!isblank(s))
    {
        sscanf(s,"%s%s",dict[n][0],dict[n][1]);
        ++n;
        gets(s);
    }
    sort(0,n-1,dict);
    while(scanf("%s",s)!=EOF)
    {
        int k=find(s);
        if(k<0)
            printf("%s\n","eh");
        else
            printf("%s\n",dict[k][0]);
    }
    return 0;
}

参考答案(时间最优[248]):

#include <stdio.h>
#include <stdlib.h>

struct ddd {
   char eng[12], pig[12];
} d[100000];

int nd, i,j,k;
char buf[10000];

compar(struct ddd *a, struct ddd *b) {
   return strcmp(a->pig, b->pig);
}

main(){
   while (gets(buf) && buf[0]) {
      sscanf(buf,"%s %s",d[nd].eng,d[nd].pig);
      nd++;
   }
   qsort(d,nd,sizeof(struct ddd),compar);
   while (gets(buf)) {
      struct ddd b, *p;
      strcpy(b.pig,buf);
      p = bsearch(&b,d,nd,sizeof(struct ddd),compar);
      if (p != NULL) printf("%s\n",p->eng);
      else printf("eh\n");
   }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞