zcmimi's blog

arrow_backhash共16篇文章

avatar
zc
2020-10-13 19:58:29

查看原题

点击跳转

f[i][j]表示用完前i个通配符,是否能匹配[1,j],

s为含通配符字符串,t为目标字符串,p_i为第i个通配符的位置

下文x|=y表示: 若y能,则x也能

若第i个通配符为*,*可以代替j之后的所有字符

那么f[i][j]|=f[i][j-1],也就是用*继续匹配下去(j-1位之后用*匹配)

s[p_i+1,p_{i+1}-1]=t[j+1,j+p_{i+1}-p_i-1],

那么f[i+1][j+(p_{i+1}-1)-(p_i+1)+1+[s[p_{i+1}]=?]]|=1

其中[s[p_{i+1}]='?']s[p_{i+1}]?时为1,否则为0

详见代码

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

异或一个数两次,可以抵消

我们可以给区间中所有相同的数都赋一个新的随机数值,防止异或时出现干扰

pre_ii位置的数上一次出现的数,v_i为位置i新赋值的数,S_i为异或前缀和

若区间[l,r]中所有数出现的数出现的次数是奇数,那么S_r\oplus S_{l-1}等于\{v_i|pre_i<x,i\in [l,r]\}的异或和

枚举r,设p_x\{v_i|pre_i<x,i\in [x,r]\}异或和

那么相当于求满足S_r\oplus S_{x-1}\oplus p_x=0

r变为r+1,\{p_i|i\in [pre_{r+1}+1,r]\}异或上v_{r+1}

问题也就转化为了: 区间异或,区间查询某个数出现次数

使用分块+hash解决

avatar
zc
2020-05-02 23:47:00
查看原题

点击跳转

可以发现110\leftrightarrow 011相当于0前/后移动了2格,那么每个0位置的奇偶性是不变的

而且每个0无法移动到下一个0的后面

把这些0记录到一个序列里,然后通过哈希判断两个子串在序列中对应的部分是否相同

因为子序列的起点奇偶性不同,分别表示以起点为奇数和偶数为标准时哈希得的前缀0序列数组。

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们考虑两个断点(设为l,r)符合的条件:

每种颜色的珠子只能出现在其中一条链中

也就是若[l,r]中出现了某种颜色[l,r]也就包含了所有的这种颜色

我们可以记录颜色出现的前缀和

记录前i个位置每种颜色的出现次数,如果位置i是 颜色a[i]的最后一个位置, 就把颜色 a[i] 的结果清零。

这样若两个位置的前缀和相同,就是合法的

可以通过hash来判断,记录所有hash值,排序后统计

两个分割点 l,r 要尽可能满足 r−l 接近 \frac n2

可以用类似双指针的方式维护

这题卡hash,要双hash

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

集合hash

  1. 两个点不认识

    两个点是相似关系说明他们的所有朋友都相同,可以把一个点的朋友当成集合hash一下,然后就可以统计了

  2. 两个点认识

    两个点是相似关系说明他们的所有朋友加上对方都相同,可以把一个点的朋友加上它自己当成集合hash一下,然后就可以统计了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

考虑如何快速找出拥有(与它的前缀相同的)后缀的串。这个东西可以通过把字符串放到Trie里面。 分类两种情况,短串+长串长串+短串。对于短串+长串的情况,先将字符串按len排序,然后顺序将字符串倒着插入trie里面,并在trie中的尾节点记录hash。利用当前串作为查询串来找答案,这样能保证当前串一定是长串,并且找到的所有短串都有和它的前缀相同的后缀,所以再利用hash判断一下就可以确定拼出来的是不是回文串了。另外一个情况同理。 复杂度是O(26\sum len)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

LG 4824 [USACO15FEB]Censoring"的做法hash,kmp什么的因为数据水所以跑不满可以水过去

还是练一下AC自动机吧

解释见代码

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

hash正着来一遍和倒着来一遍就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一个区间合法,仅当这个区间中包含的颜色没在区间外出现过

我们可以把每种颜色出现的每个位置都赋值使得这些位置上的值加起来为0

这样我们就可以用前缀和的方式统计了

1/2
Search
search