《Hash与位运算.ppt》由会员分享，可在线阅读，更多相关《Hash与位运算.ppt（32页珍藏版）》请在三一文库上搜索。
1、Hash与位运算 山东师大附中 陈键飞 位运算 对二进制数的一些操作 优化时间常数 优化代码长度 核心思想 将一个二进制串(集合)用一个数表示 集合1,2,3,5 (10111)2 位运算符 and( writeln(m+1)shl n); shr的应用 Div 2k ：A shr k mid:=(lb+rb)shr 1; if (leftmid) then search(t shl 1+1,mid+1,rb); 小例题 缩短代码： 集合a是不是集合b的子集？ function a( a,b : array1.30of boolean):boolean; var i:longint; begi
2、n for i:=1 to 30 do if ai and not bi then exit(false); exit(true); end; a and b = a 例题 判断一个01串中有没有两个1相邻？ function b( a:array1.30of boolean):boolean; var i:longint; begin for i:=1 to 29 do if ai and ai+1 then exit(true); exit(false); end; 如果是判断是不是有两个0相邻呢? a and (a shr 1) 0 a or (a shr 1) 0 do begin i
3、nc( popcount , x and 1) ; x := x shr 1 ; end ; end ; O(log x) 例题 function popcount2( x : longint ) : longint ; begin x := ( x and $55555555 ) + ( (x1) and $55555555 ) ; x := ( x and $33333333 ) + ( (x2) and $33333333 ) ; x := ( x and $0F0F0F0F ) + ( (x4) and $0F0F0F0F ) ; x := ( x and $00FF00FF ) +
4、( (x8) and $00FF00FF ) ; x := ( x and $0000FFFF ) + ( (x16) and $0000FFFF ) ; exit( x ) ; end ; 例题 状态压缩的动态规划 A包含于B：A and B = A Hash 状态 对一个事物的一个完整的描述 比如说集训班有三个人，其中李其乐是神 牛，李其刚是神犇，羊驼是李振 那么(李其乐=神牛，李其刚=神犇，羊驼= 李振)就是一个状态 Hash 再比如说，昨天所有同学的考试成绩，也 是一个状态 如果有N个同学，这个状态的大小就是O(N) Hash Hash函数与Hash表 Hash函数：一个状态到一个正整
5、数的映射 F(Status) Hash表：将Hash函数按值的大小索引 Hash Hash的应用是多种多样的 应用方法上：仅Hash函数，仅Hash表，两 者都用 应用领域上：广搜的判重，字符串的索引 仅用Hash函数 在下载时经常用到的MD5：将一个文件映 射到一个Hash函数，通过比较MD5校验码 判断文件的完整性。 仅用Hash函数 一个信息学竞赛中的应用实例： Rabin-Karp算法 Hash表 利用Hash函数值的特殊性，实现高效的插 入、删除、查找。 典型的空间换时间 Hash表 若Hash表大小是L，共S个状态 插入复杂度O(1),删除和查找O(S/L) 对比二叉查找树 插入，
6、删除和查找O(log n) Hash表的应用 POI2000，Promotion值域缩小版 Hash函数和Hash表的综合应用 广搜的判重：先将状态映射成Hash函数， 再用Hash表插入，查找。 广搜+Hash已经成为一种套路，两者是密不 可分的 Hash函数和Hash表的综合应用 字符串的索引 生物基元问题： 给定字符串S和基元串A1An，求最大的k ，使S1.k由基元串组成 Hash函数和Hash表的综合应用 Fi=Or(Fj) (当且仅当j=i且Sj+1.i是一 个基元串) Hash优化决策时间：判断Sj+1.i是不是基 元串O(1) 一个应用 给定n个l位k进制数，求最大的一段数，使 得这段数每位的和都相等。 小总结 Hash的用法是灵活多变的，在一个题没有 思路时，不妨想想Hash Hash+位运算 CowXor 有N个数，每个数220 求一段数，使得这段数的异或值最大