menu zcmimi's blog

矩阵乘法

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

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

include<bits/stdc++.h>

define fur(i,x,y) for(in

zc
2020-05-29 17:09

SPOJ的GSS系列是关于区间统计技巧的集合

GSS1,GSS3: 最大子段和:

每个节点记录区间和,最大后缀和,最大前缀和,答案

```cpp node operator+(node x,no

zcmimi
2020-05-25 19:22

数据结构
    • [ ] 单调栈
  • 队列

    • [ ] 单调队列
    • 优先队列
    • 双端队列
zcmimi
2020-05-18 21:43

有多种做法

AC自动机暴力

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

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

AC自动机暴力

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

对点名串建立AC自动机

zc
2020-05-17 16:09

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

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

include<bits/stdc++.h>

define gc get

zc
2020-05-16 21:36

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

include<bits/stdc++.h>

const int N=100011; char s[N]; int

zc
2020-05-16 14:13

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

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

那么在height中也是连续的

那么我们只需要求出 height数组中 连续k-1个数中 最小的数 最大

zc
2020-05-16 14:13

```cpp

include<bits/stdc++.h>

define fur(i,x,y) for(int i=x;i<=y;++i)

const int N=1000001; char s[

zc
2020-05-16 14:13

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

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

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

zc
2020-05-16 14:13

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

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

然后求出sa,rnk,height数组

我们要找出cnt个所属字符串不同的后缀,让他们$\opera

zc
2020-05-16 14:13
2 / 63
Search
search