冷滟泽的个人博客

2020-03-02 lengyanze 阅读(38) 评论(0)

比赛时并没有搞出来qwq 题目中的两种变换可以当作是字符 1 或 0 的一次运动。而我开始只去考虑了 1 的运动，而忽视了 0 的运动。实际上 0 的运动规律是更容易找到的。 观察到 011\to 110 可以看作 ...

2020-03-01 lengyanze 阅读(43) 评论(0)

广义后缀自动机是后缀自动机（SAM）的多串扩展。它可以识别一棵 Trie 树上从根到任意一点的路径。 广义 SAM 的每个状态同样由转移边 trans[]，parent 链 par 以及该状态所表示的最长子串 len...

2018-12-16 lengyanze 阅读(98) 评论(0)

题目链接 BZOJ2754 Luogu2336 概述 本题解法众多，比如： AC 自动机 广义后缀自动机 后缀数组 + 莫队 ...... 这里我介绍一种新的解法：后缀数组 + ST 表 + 二分 +...

2018-12-13 lengyanze 阅读(76) 评论(0)

定义 后缀 i ：一个字符串从第 i 个字符到结尾的子串成为这个字符串的后缀 i ； 后缀排序：将一个字符串的所有后缀按字典序排序； sa[i] ：后缀排序后排名第 i 的后缀； rank[i] ：后...

2018-12-12 lengyanze 阅读(71) 评论(0)

题目链接 传送门 题目大意 有 n 张卡片，每张卡片上有一个序列，求这些序列最长相同子串的长度。两个子串相同定义为两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。 问题转化 为了处理题目中定义的“相同”...