冷滟泽的个人博客

2019-02-21 lengyanze 阅读(41) 评论(0)

题意 给出两个字符串 A, B ，求这两个字符串长度不小于 k 的公共子串的个数。两对公共子串不同当且仅当子串在字符串的位置不同。 思路 后缀数组 + 单调栈； 把两个字符串连接起来，中间用分隔符隔开，做后缀排序；...

2019-02-19 lengyanze 阅读(43) 评论(0)

题意 枚举字符串 s 的每一个本质不同的子串 ss ，令 cnt(ss) 为子串 ss 在字符串 s 中出现的个数，求 \sum \frac{cnt(ss)\times [cnt(ss)+1]}{2} 思路 将 s...

2019-01-01 lengyanze 阅读(52) 评论(0)

题目链接 Luogu3302 BZOJ3213 题意 给出一堆森林（每个点有权值）和两种操作： 在点 x 和点 y 间连一条边，保证操作后图还是森林； 询问点 x 与点 y 之间路径上第 k 小的权值，保证 x...

2018-12-23 lengyanze 阅读(33) 评论(0)

题目链接 BZOJ4650 Luogu1117 算法分析 以下内容部分借鉴于 Sengxian's Blog 。 将以 i 开始 AA 串的个数记为 f[i] ，以 i 为结束的 AA 串的个数结尾 g[i] ；...

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

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