「算进」[基构]HASH

首先,「算进」是什么?
就是《算法竞赛进阶》,大神写的书,一个蒟蒻怎么能不好好磕一下呢,于是就有了这第一篇文章。
[基构]是什么?
就是基础数据结构的意思呢,基础不扎实就要好好学基构。
从我最不好的地方开始学习,来Hash把!

Hash表

哈希表又被人叫做散列表,一边有哈希函数与链表结构互相实现,与离散化思想类似,当我们要对若干信息进行统计时,我们可以通过哈希把复杂的信息维护到一个及其容易维护的值域里,因为值域范围更小,信息更少,所以更容易处理,但是hash可以回产生多个数对应一个值的问题,那么我们就要建立链表结构来处理这样的问题,把hash值相同的接上去。
Hash表主要有下面两种基本操做
1. 计算哈希函数的值以映射区间
2. 定位到链表中依次遍历比较
在Hash函数设计较好时,原始信息可以很均匀的分布在各个表头,表头数组长度都是O(n)级别的,且Hash函数分布均匀几乎不产生冲突所以的话查找统计的复杂度接近O(1)

Snowflake Snow Snowflakes

这题的话就是明显可以用哈希表来做啦,对于两篇形状相同的雪花,那么他们的乘积也是一样的,但是又为了避免偶然,所以哈希函数的计算中增加了他们的和,Hash(x)=sum(x)+mul(x)这样就可以很好的做统计了。
AcceptCode

字符串Hash

字符串Hash可以理解为吧一串字符串映射成一个飞负整数,最简单的做法就是吧字符串转换为P进制的数字,然后再取Mod,一般来说P我们取13113331,这个时候的Hash值冲突是最低的,这时只要Hash值相同吗,我们就可以认为原字串是相等的,通常我们P2^{64},即直接用unsigned long long类型来储存,这样可以让Hash值自然溢出,自然溢出也就是自动对2^{64}进行取模,避免了低效的取Mod运算
留个坑让我去测试
在极限数据之下,我们可以同时取多个质数P来计算多个Hash值,当所有Hash值都满足时才判为相同,这样可以避免一些极端数据。
通过这个,我们还可以快速O(n)跑出整个字串的所有子串的Hash值。
假设我们已知字符串S的Hash值为H(S),那么在他后面加一个符号C的Hash值为H(S+C)=(H(S)*P+value[C]) Mod M,这就相当于在P进制下面对字串S向左移一位,然后加上C的值。
那么已知字符串S的Hash值为H(S),字符串S+T的Hash值为H(S+T),那么字符串T的值H(T)=(H(S+T)-H(S)*P^{length(T)}
也就是通过P进制下在S后面补0的方法,把S左移到S+T的左端对齐,然后二者相减得到阞H(T)
这样就可以做到O(n)构造O(1)查询Hash值了。

兔子与兔子

这题的话很好解,先预处理一下再暴力求值。
记我们选取的DNA序列为S,根据我们刚才提到的字符串Hash算法,设F[l]表示前缀子串S[1 ~ i]的Hash值,有F=[F-1]*131+(S[i]-"a"+1)于是可以得到任一区间[l,r]Hash值为F|r]-F|l-1]*131^{r-l+1}。当两个区间的Hash值相同时,我们就认为对应的两个子串相等。整个算法的时间复杂度为O(|S|+Q)
AcceptCode

Palindrome

P站炸裂先弃个坑
这题有思路了,先搁着,利用兔子与兔子,再加上二分最大值,然后就可以了,我们这样就可以求出区间最大的是哪个。算法复杂度O(nlog(n))

后缀数组

这题也是没有题目和数据的,那么,先把东西写着,怎么用HASH+二分求得后缀数组的SA和Height数组,期待一下。

发表评论

电子邮件地址不会被公开。 必填项已用*标注