Luogu P7863 「EVOI-RD1」飞鸟和蝉
题目描述
https://www.luogu.com.cn/problem/P7863
简要题意:给定一张 $n\times m$ 的四连通网格图,每个点有一个权值 $a_{i,j}$,每个点只能走到周围四连通中权值严格小于自己的点,或者花费 $a_{i,j}-a_{x,y}$ 的代价从 $(i,j)$ 走到 $(x,y)$,现给定起点 $(x_0,y_0)$,求最少使用多少次第二种操作使得从起点开始经过每个点恰好一次且最终最后到起点,在最小化第二种操作的情况下,最小化代价
$n,m\le 50$
Luogu P5576 [CmdOI2019]口头禅
题目描述
https://www.luogu.com.cn/problem/P5576
简要题意:给定 $n$ 个只有 $01$ 的字符串以及 $m$ 次询问,每次询问 $[l,r]$ 的所有字符串的最长公共子串的长度
$n\le 2\times 10^4,m\le 10^5,L\le 4\times 10^5$
Luogu P6640 [BJOI2020] 封印
题目描述
https://www.luogu.com.cn/problem/P6640
简要题意:给定两个字符串 $S,T$ 和 $q$ 次询问,每次询问 $S[l\cdots r]$ 和 $T$ 的最长公共子串长度
$|S|,|T|\le 2\times 10^5,q\le 2\times 10^5$
CF 587F Duff is Mad
题目描述
https://www.luogu.com.cn/problem/CF587F
简要题意:给定 $n$ 个字符串 $S_i$,$m$ 次询问 $S_l,S_{l+1},\cdots,S_r$ 在 $S_k$ 中出现的次数和
$n,m,\sum|S|\le 10^5$
CF 547E Mike and Friends
题目描述
https://codeforces.com/problemset/problem/547/E
简要题意:给定 $n$ 个字符串 $S_i$,$m$ 次询问 $S_k$ 在 $S_l,S_{l+1},\cdots,S_r$ 中出现的次数和
$n,\sum|S|\le 2\times 10^5,m\le 5\times 10^5$
Luogu P5840 [COCI2015]Divljak
题目描述
https://www.luogu.com.cn/problem/P5840
简要题意:一开始现给定 $n$ 个字符串 $S_i$,同时有一个字符串集合 $P$,一开始是空的,接下来有 $m$ 次两种操作,第一种是向集合中添加一个字符串 $T$,第二种是查询 $S_k$ 是集合 $P$ 中多少串的子串
$n,m\le 10^5, \sum |S|+\sum|T|\le 2\times 10^6$
Luogu P3426 [POI2005]SZA-Template
题目描述
https://www.luogu.com.cn/problem/P3426
简要题意:给定一个字符串 $S$,例如有一个 $aba$ 的印章,我们可以用这个印章完成 $ababa$ 的印刷,中间的 $a$ 被印了两次,但是同一位置上印不同字符是不行,求一个长度最小的印章
$n\le 5\times 10^5$
Luogu P3538 [POI2012]OKR-A Horrible Poem
题目描述
https://www.luogu.com.cn/problem/P3538
简要题意:给定字符串 $S$ 和 $m$,接下来有 $m$ 次询问,每次求 $S[l\cdots r]$ 的最短循环节长度,这里的循环节的定义为如果 $t$ 是 $S$ 的循环节,则 $S$ 由 $t$ 重复若干次得到
$n\le 5\times 10^5,m\le 10^6$
Luogu P7114 [NOIP2020] 字符串匹配
题目描述
https://www.luogu.com.cn/problem/P7114
简要题意:给定一个字符串 $S$,求 $S$ 的所有合法的 拆分方案,$S$ 的一个拆分我们定义为 $S=(AB)^kC$,其中 $A,B,C$ 均为非空字符串,且 $A$ 中出现奇数次的字符数量不超过 $C$ 中出现奇数次的字符数量,$k$ 为正整数,两个方案不同当且仅当 $A,B,C$ 至少一个字符不同
$T\le 5,S\le 2^{20}$