冷滟泽的个人博客

2019-02-28 lengyanze 阅读(37) 评论(0)

题意 给出一个串 A 和 n 个串 Bi ，求 A 中不在任何一个 Bi 中出现的本质不同的子串的个数。 思路 后缀数组 + 单调栈; 把 A 和所有 Bi 拼接在一起，用间隔符分隔后做后缀排序并求出 height...

2019-02-24 lengyanze 阅读(71) 评论(0)

题意 给出一个长度为 n 的字符串 s 和 q 次询问，每次询问给出两个集合 A,B ，求 \sum_{i\in A}\sum_{j\in B} lcp(i,j) 思路 求后缀之间的 LCP 之和，自然地想到使用后...

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-22 lengyanze 阅读(53) 评论(0)

[树套树学习笔记]() 一、线段树/树状数组套平衡树 既然是“线段树套平衡树” ，就先建一颗线段树： 它的每个结点都是一颗平衡树，这颗平衡树就维护该节点所表示的区间： 但是线段树的每个结点都套一颗平衡树，空间会不...