IAML's Blog

Find passion in coding
poj2002 Squares
poj3274 Gold Balanced Lineup

poj2503 Babelfish

IAmL posted @ 2009年4月03日 05:25 in 解题报告 with tags poj2503 Babelfish解题报告 , 3007 阅读

很郁闷,在这样的水题上耗费了将近3个小时~看来我还是太水了~。这题基本上没什么技术含量,唯一一个难点不是算法,而是读入(主要是判断空行……)。之后把读入的两个数组放在hash中。这里用的hash函数是常用的ELFhash,虽然说这个函数能极大地避免重复映射,但是还是存在冲突的可能性,所以要注意写上冲突后的处理方法。之后就是读入要查找的字符串,然后在hash中查找(我就是这部分写得不够好,导致调试了n久……

后记:

1.本题除了用hash,还能用排序+二分搜索来写。(当然速度上就肯定比不上hash啦)

2.可以粗暴地用map来做。但是这样一来这题就成为真正的水题了……

========不华丽的分割线===========

 

#include <iostream>
using namespace std;

#define N 100001
#define strSize 15

struct hash
{
        bool used;
        char fo[strSize], en[strSize];
        hash *next;
        hash(){used = false; next = NULL;}
        hash(char *f, char *e)
        {
                int i = 0;
                while (*f) fo[i++] = *f++;
                fo[i] = 0;//设置字符设串的结束标志

                i = 0;
                while (*e) en[i++] = *e++;
                en[i] = 0;
               
                used = false;
                next = NULL;
        }
}h[N];

int ELFhash(char *key)
{
        unsigned long g, h = 0;

        while (*key)
        {
                h = (h << 4) + *key++;
                g = h & 0xF0000000L;

                if (g) h ^= g >> 24;

                h &= ~g;
        }

        return h % N;
}

int main()
{
        char *c1, *c2, tmp, en[strSize], fo[strSize];
        hash *p;
        bool found;
        int key, i;

        while (1)
        {              
                tmp = getchar();

                if (tmp == '\n') break;//判断是否是空行

                en[0] = tmp;
                scanf("%s%s", en + 1, fo);     
               
                tmp = getchar();

                key = ELFhash(fo);
                if (!h[key].used)
                {
                        h[key].used = true;
                        i = 0;
                        c1 = en;
                        while (*c1)     h[key].en[i++] = *c1++;
                        en[i] = 0;
                       
                        c1 = fo;
                        i = 0;
                        while (*c1) h[key].fo[i++] = *c1++;          
                        fo[i] = 0;
                }
                else//处理重复冲突的情况
                {
                        p = &h[key];
                        while (p->next != NULL) p = p->next;

                        p->next = new hash(fo, en);
                }
        }
       
        while (scanf("%s", fo) != EOF)
        {
                key = ELFhash(fo);
               
                if (!h[key].used) printf("eh\n");
                else
                {
                        p = &h[key];
                        while (p != NULL)
                        {
                                found = true;

                                c1 = fo;
                                c2 = p->fo;

                                while (*c1 && *c2)//判断字符窗是否相等
                                {
                                        if (*c1++ != *c2++)
                                        {
                                                found = false;
                                                break;
                                        }
                                }

                                if (found && !(*c1) && !(*c2))
                                {
                                        printf("%s\n", p->en);
                                        break;
                                }
                               
                                p = p->next;               
                        }

                        if (p == NULL) printf("eh\n");
                }
        }

        return 0;
}

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter