poj2503题目意思很简单:就像查找一本字典,根据输入的条目和要查询的单词,给出查询结果(每个单词长度不超过10)。这题有很多实现方式,最容易想到的就是map,但这是acm训练且stl里面的map速度不够快,那就要另谋出路。
数据量为100,000。可以想到的是快排+二分,复杂度是O(nlog2n)。还有就是哈希,哈希查询时间是O(1),当然,还要考虑哈希冲突,设计合理的字符串哈希函数。
首先是快排+二分,比较简单。
#include <iostream>
const int MAX = 100001;
typedef struct
{
char e[11];
char f[11];
}Entry;
Entry entry[MAX];
int i = 0; //词典总条数
int cmp(const void *a, const void *b)
{
return strcmp((*(Entry *)a).f, (*(Entry *)b).f);
}
int BinSearch(char c[])
{
int low = 0, high = i - 1;
int mid, t;
while(low <= high)
{
mid = (low + high) / 2;
t = strcmp(entry[mid].f, c);
if(t == 0)
return mid;
else if(t == -1)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main()
{
char str[25];
int index = -1;
while(gets(str))
{
if(str[0] == '\0')
break;
sscanf(str,"%s%s",entry[i].e,entry[i].f);
i++;
}
qsort(entry,i,sizeof(Entry),cmp);
while(gets(str))
{
index = BinSearch(str);
if(index == -1)
printf("eh\n");
else
printf("%s\n",entry[index].e);
}
return 0;
}
对于字符串的哈希,在《算法艺术与信息学竞赛》推荐使用ELFHash函数。对于哈希冲突的处理,采用的是链表法(个人认为线性探测等效率不是很高)。
#include <iostream>
const int M = 149993;
typedef struct
{
char e[11];
char f[11];
int next;
}Entry;
Entry entry[M];
int i = 1; //词典总条数
int hashIndex[M];
int ELFHash(char *key)
{
unsigned long h=0;
while(*key)
{
h=(h<<4)+(*key++);
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%M;
}
void find(char f[])
{
int hash = ELFHash(f);
for(int k = hashIndex[hash]; k; k = entry[k].next)
{
if(strcmp(f, entry[k].f) == 0)
{
printf("%s\n",entry[k].e);
return;
}
}
printf("eh\n");
}
int main()
{
char str[22];
while(gets(str))
{
if(str[0] == '\0')
break;
sscanf(str,"%s %s",entry[i].e,entry[i].f);
int hash = ELFHash(entry[i].f);
entry[i].next = hashIndex[hash];
hashIndex[hash] = i;
i++;
}
while(gets(str))
find(str);
return 0;
}
分享到:
相关推荐
北大POJ初级题-数据结构:解题报告+AC代码
北大POJ2503-Babelfish 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
北大POJ1002-487-3279【Hash+Qsort】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ中级搜索全部练习【解题报告+AC代码】
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
选择了三道经典的二分查找的poj模拟题,有利于读者对二分查找的深刻把握
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
NULL 博文链接:https://128kj.iteye.com/blog/1759266
北大POJ3096-Surprising Strings 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1750462
NULL 博文链接:https://128kj.iteye.com/blog/1734586
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
NULL 博文链接:https://128kj.iteye.com/blog/1754756