ACM必做50题的解题-快速查找(B-Search,Hashandsoon).docVIP

ACM必做50题的解题-快速查找 (B-Search, Hash and so on).txt你不能让所有人满意，因为不是所有的人都是人成功人士是—在牛B的路上，一路勃起你以为我会眼睁睁看着你去送死吗？我会闭上眼睛的POJ 2503 Babelfish 题目大意很简单，就是给你字典的对应信息，然后给你查询条件要求你输出字典查询结果，如果字符串没有在字典中则输出eh。 恩，学到了一个新的函数bsearch()，可以进行二分查找。先对字典使用qsort排序然后再使用bsearch()查找字符串即可。 还学到了一个输入函数sscanf()，可以从一个字符串中读取内容，格式如下 sscanf (string str, string format [, string var1...]) #include stdio.h #include stdlib.h #include string.h typedef struct { char en[11]; char fn[11]; }dict; dict a[100001]; /* 定义qsort比较函数 */ int q_cmp(const void * a,const void *b) { return strcmp(((dict*)a)-fn, ((dict*)b)-fn); } /* 定义bsearch比较函数 */ int b_cmp(const void* a, const void* b) { return strcmp((char*)a, ((dict*)b)-fn); } int main() { char str[30]; int i, sign; dict *p; i = 0; /* 查询标记记为未开始 */ sign = 1; /* 读取字符串直到文件结束 */ while(gets(str)) { /* 遇到空行则开始排序字典 */ if (str[0] == \0) { /* 查询标记记为开始 */ sign = 0; qsort(a, i, sizeof(dict), q_cmp); continue; } /* 查询未开始时读取字典信息 */ if (sign) { /* 使用sscanf从str中读取查询要求 */ sscanf(str, %s %s, a[i].en, a[i].fn); i++; } /* 查询开始时进行查询 */ else { /* 二分查找指定字符串 */ p = (dict*) bsearch(str, a, i, sizeof(dict), b_cmp); /* 找到则输出结果 */ if (p) { puts(p-en); } /* 找不到输出eh */ else { puts(eh); } } } //system(pause); return 0; } POJ 2513 Colored Sticks 欧拉通路+并查集+trie树 这道题大意是：已知有n根木棒，每个木棒有两种颜色表示两端，问：能不能将所有的木棒连接成一条直线（连接处颜色相同）。 可以考虑无向图的欧拉通路问题：将每种颜色看成图中的一个节点，木棒看作连接节点的边，于是判断两点： 1，每种颜色（节点）的度 2，是否为连通图 首先，每种颜色的度可以通过每条木棒的两端颜色的累积得到，问题是，每种颜色都是字符串，怎么关联每种颜色和度呢？ 最容易想到的是Hash，这肯定是可行的。例如degree [ hash(red) ]=5。表示颜色为红色的度为5。 但是，既然提示用trie树来做，那么trie树的节点的数据域就可以保存每种颜色的id（相当于分配的hash值，可以通过一个全局变量自增产生），这样经过将每种颜色字符串插入到tree中以后，通过trie树的search操作就能高效的获取每种颜色对应的id，没插入一种颜色，为其产生一个id，只需要注意相同颜色插入时的处理即可。 其次，判断无向图是否连通可以使用并查集来判定：经过n-1各union操作后，所有节点都在一个集合（树形结构表示集合的话，即所有节点的父节点（集合代表）都一样）。由于每种颜色是由字符串来标示的，每个集合保存颜色对应的唯一id。 通过上面两个步骤的判定，就可以得出结果。 #include iostream #include cstring using namespace std; const int max_size=500001;