2020.7.18 牛客多校第三场

2020.7.20 牛客多校第四场

bitset：

[JSOI2010]连通数

牛客第三场J

[SHOI2009]会场预约

百度之星初赛第一场 rk:158 pros:5/5/8

codeforces Round 658

没有专题

没有比赛

没有专题

没有比赛

补题，本周牛客第四场的C，广义SAM（题解）做法
链接
题意：求一个串(n~1e5)的所有子串$s_i$,经过$f(s_i)$后产生的所有不同子串数量，字符集大小$|T|=10$ 记$s_i=S_x\sim S_y,f(s_i)$返回一个字符串,第$i$位为$max_{S_x,. . .,S_i}$
思路：题意等价于找所有后缀的$f(s_i)$的不同子串数量。考虑到长度更长的后缀会使整个串变化，变化的位数O(n)，变化最大次数=字符集大小$|T|$，因此SAM上结点数量$O(n|T|^2)$，可以用广义SAM跑下来。每次记录一下不同类结点最初插入自动机的位置，变化时直接从该位置向后插入

推荐另外一道SAM相关的题
链接
tag:字符串，dp
题意：给一个长为n的串S，求最长的字符串序列$S,S_1,..,S_k$,满足其中每一个串都在前一个串中出现至少2次
做法：比较容易想到的做法是在SAM的parent树上从根向下找出现次数>2的点，但并不能满足父亲结点在儿子结点中出现至少两次的要求。 需要用线段树维护一下串的特定范围上（parent树上结点的长度范围），各个点的endpos，来确定是否满足要求并转移 comment：似乎比较少见的SAM题