Hash在ACM竞赛中的应用

单击鼠标编辑标题文的格式,单击鼠标编辑大纲正文格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,*,Hash在ACM竞赛中的应用,doraemonokNKACM,1,排序,“基于比较的”排序复杂度下界是O(nlogn),但对于某些情况可以更快,现有N个整数，范围在0至10000，如何排序？,建立数组int num10001，初始化为0，numi表示有多少个数等于i,读入一个数a，则numa+,可以达到O(n)复杂度，这个思想就是hash,2,Hash的思想,将某个对象对应到一个关键值，然后通过关键值归类，放入到一个表中（哈希表），今后可以根据关键值迅速查找,Hash可以用来判重和统计数目,3,Hash中的冲突问题,如果刚才的数据范围是1至1010，则范围过大，可以对数据取模p，得到一个较小的数字key，作为关键值，再插入到Hash表，则Hash表的大小只需要等于key。,p一般选择为较大的素数，或者也可以改为计算&0x1fffff等类似方法避免取模运算较慢的问题,但是这样就会出现两个不同的数对应到同一关键值，例如0和p，我们将Hash表的每一个位置做成一个链表，插入到链表中即可。这叫做开散列法。,4,字符串Hash,Hash中最常用的是字符串Hash,将一个字符串对应到一个整型数值，插入到哈希表,对应方法有很多种，甚至可以根据问题的特殊性自己构造，常用的有Rabin-Karp，ELFHash,5,Rabin-Karp,如果字符串中可能出现的字符有k个，则可以将字符串对应到k进制数,例如，如果字符串只可能为小写字母组成，则acm就对应到0262+2*26+12,log(263)/log(26)=13.40307719,当字符串长度不超过13的时候，用long long作关键值类型，加上字符串长度作为限制，每个字符串唯一对应关键值,当字符串长度超过13的时候，就要进一步验证,6,Hash冲突的判断,如果链表中有值，不代表一定是你要找的字符串,两种方法可以进一步判定1,逐个字符比较字符串2,建立另外一个或者多个hash函数，比较他们的其他hash关键值是否相同,7,ELFHash,参考黑书96页,黑书中推荐此法，据说效果不错，不过我没用过,8,其他字符串Hash方式,加法acm - a + c + m优点：计算方便，快缺点：容易冲突，acm = cam = bbm,乘法acm - a * c * m比加法冲突略少,上述两种方法可以用于忽略顺序的hash，如判定集合相同。,其中乘法可以利用优化将各字母对应到素数,9,数同构的hash,给定两个树，兄弟节点之间无顺序关系，要求判定两树是否同构,可以给每个叶子节点赋相同的值，并给出一个公式，用于通过叶子节点的值计算父亲节点的值,公式需要满足可交换性，如乘法，但建议使用更复杂的公式。如果公式不满足交换性，也可考虑对所有叶子节点排序后使用公式。,10,公式的hash,判定公式是否成立,例如判定(a+b) * c = a * c + b * c,如果你有时间并且有精力，可以写个程序从数学角度判定公式是否成立,可以将每个变量对应到一个随机的值，然后计算两边值是否相等,如果怕RP不好，比如如果a=1,则a*b=b也被判定为成立，可以多随机几次,11,其他结构的hash,给定N个点的坐标，求可以构成多少个正方形？长方形？平行四边形？,可以将任意两个点的中点进行hash，也可以再加上其他值一起hash，之后只要对很少一部分验证是否构成所需的图形即可,12,推荐题目,POJ 1200 Crazy Search （Rabin-Karp）,POJ 1635 Subway tree systems （树同构）,POJ 1971 Parallelogram Counting （统计平行四边形）,POJ 2002 Squares （统计正方形）,POJ 3504 Obfuscation （忽略顺序的字符串hash）,POJ 1690 (Your)(Term)(Project) (公式Hash）,POJ 2549 Sumsets,13,寒假集训,训练人数少，训练强度大,寒假训练后的队员基本都可以参加,ICPC,条件：基本功扎实，,C/C+,熟练,以上两页共含200题，中文题目为主，难度小,如果某个题目实在做不出，也可以向我们询问思路,要求通过30题有资格参加寒假集训，通过60题一定可以参加寒假集训，截止到12月31日,建议有能力的同学到做题，做出相同数目的题目也一样可以参加集训,14,