zcmimi's blog
avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

可以考虑把字符串倒序

这样添加一个字母相当于增加了一个后缀,相对原来更好处理

可以发现在插入新的字符串时,height改变的只有height[pre],height[p],height[nxt]

通过平衡树动态维护这三个位置就可以了

avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

40%的log n做法挺容易的,就是一直往右儿子走,走到叶子就往左走,一直重复即可

100%的做法:

首先可以把f(l)\bigoplus\dots\bigoplus f(r)变成

[f(1)\bigoplus f(2)\bigoplus\dots\bigoplus f(r)]\bigoplus[f(1)\bigoplus f(2)\bigoplus\dots\bigoplus f(l-1)]

显然f(2^k)=f(2^k+1)=2^{k+1}-1

接着可以发现\forall k,1\le t\le 2^k-1,f(2^k+2t)=f(2^k+2t+1)

因为最下一层没有填满整一层,只填满了根节点的左子树,根节点的右子树并没有发生变化

剩下的f(n)就需要考虑一下了

首先算出树的深度(根节点深度为0)

左边: 即使没占满也全算

右边: f(n/2)

avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

矩阵乘法

这题倍增加速比快速幂快,可以节省很多多余的计算

二进制拆位后才能矩阵运算

avatar
zc
2020-05-17 16:09:00
查看原题

点击跳转

有多种做法

AC自动机暴力

AC自动机+树状数组+lca+dfs序

后缀数组+ST表+树状数组

AC自动机暴力

原数据可以过,后来添加了加强数据就tle了

对点名串建立AC自动机,枚举名字在上面匹配,跳fail树统计

记得用于标记是否访问的数组不能用memset清零,要按原来的修改回去

玄学复杂度

avatar
zc
2020-05-16 21:36:00
查看原题

点击跳转

相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串

那么我们差分之后再判断即可

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

\frac {n(n+1)}2 - \sum height[i]

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

首先用后缀数组求出height数组

可以发现,重复出现的子串在sa数组中一定是连续的

那么在height中也是连续的

那么我们只需要求出 height数组中 连续k-1个数中 最小的数 最大可以是多少 即可

单调队列就可以解决

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

看到环就想到把原串变成两倍,而这对被延长了的原串中的子串在sa中的排名没有影响

比如baba变成babadfasdfa,这并不会影响到baba的排名

那么直接求出sa后输出即可

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

连接所有字符串(cnt个),中间用特殊字符隔开

给每个位置标记所属字符串

然后求出sa,rnk,height数组

我们要找出cnt个所属字符串不同的后缀,让他们\operatorname{LCP}最长

可以用双指针+单调队列的方式实现

单调队列记录当前区间最小的height,单调递增,双指针移动右指针的同时维护单调队列,移动右指针后判断是否可以移动左指针,并重复到无法移动,同时对应弹出单调队列的队头

18/74
Search
search