walkalone

分类

题解(77)

/ 注册

全部文章（共9篇）

题解 | 2023 年牛客多校第三场 G 题 Beautiful Matrix

题意：给定一个 n×mn\times mn×m 的字符矩阵 {S}(i,j)=(1,1)(n,m)\{S\}_{(i,j)=(1,1)}^{(n,m)}{S}(i,j)=(1,1)(n,m)，定义一个 n×nn\times nn×n 的子矩阵是优美的当且仅当 ∀i,j∈[1,n]\forall i...

字符串 Manacher

2023-07-25

2 614

2022 年牛客多校第一场补题记录

A Villages: Landlines 题意：有一个电站位于 xsx_sxs，需要在 [xs−rs,xs+rs][x_s-r_s,x_s+r_s][xs−rs,xs+rs] 的范围内设置至少一个电塔将电引出。n−1n-1n−1 个用电处位于 xix_ixi，需要在其范围 [xi−ri...

动态规划贪心数据结构字符串

2022-09-08

0 414

2022 年牛客多校第十场 D 题题解

D Mi Re Do Si La? So Fa! 题意：给定串 SSS，询问其每个子串的完整循环节长度和。例如串 aaaa的完整循环节长度有 1,2,41,2,41,2,4 三种。∣S∣≤1×106|S| \leq 1\times 10^6∣S∣≤1×106。解法：显然每个子串 S[l,r]S[l...

字符串 RMQ 数据结构

2022-08-27

1 353

2022 年牛客多校加赛场 C 题题解

C Cmostp 题意：给定字符串 SSS，qqq 次询问 SSS 的全部本质不同子串中有多少个子串的右端点落入 [l,r][l,r][l,r] 中的。 ∣S∣,q≤5×105|S|,q \leq 5\times 10^5∣S∣,q≤5×105。解法：显然在 SAM 上可以将前缀 [1,i][1,...

数据结构字符串

2022-08-26

0 299

2022 年牛客多校第九场 G 题题解

G Magic Spells 题意：给定 kkk 个串 {Si}\{S_i\}{Si}，问在每个串中都出现的本质不同回文子串个数。∑∣Si∣≤3×105\sum|S_i| \leq 3\times 10^5∑∣Si∣≤3×105，k≤5k \leq 5k≤5。解法：kkk 较小，因而可以考虑对...

字符串回文自动机

2022-08-16

1 352

2022 年牛客多校第八场 K 题题解

K Symmetry: Convex 题意：给定 nnn 个点的凸多边形 CnC_nCn，输出前 iii 个点构成的凸包的对称轴。n≤1×105n \leq 1\times 10^5n≤1×105。解法：找对称轴可以使用 Manacher。本题先预处理整个凸包构成的串的 Manacher（注意不...

计算几何字符串

2022-08-14

0 351

牛客多校第七场 I 题题解

I 题题意：定义一个串的最小表示为——按出现某个字符第一次出现顺序从小到大的排序，并依次编号 abc⋯zabc\cdots zabc⋯z。给定串 SSS，对其全部后缀进行最小表示的排序。∣S∣≤2×105|S| \leq 2\times 10^5∣S∣≤2×105。解法：考虑朴素的后缀数组排序，即...

字符串哈希二分

2022-08-11

0 308

牛客多校第二场 F 题题解

F NIO with String Game F 题题意：给定 nnn 个串 {Tn}\{T_n\}{Tn} 和一个串 SSS，有以下四种操作：给 TxT_xTx 的末尾增加一个字符；给 SSS 串末尾删除 ppp 个字符；给 SSS 串末尾插入 kkk 个字符；查询 {Tn}\{T_...

字符串

2022-07-29

2 278

牛客多校第三场 H 题题解

题意：给定长度为 nnn 的模式串 SSS，和长度为 mmm 的权值数组 {wi}\{w_i\}{wi}。对于一个长度为 mmm 的串，wiw_iwi 表示使用该串上第 iii 个字符与 SSS 匹配可以获得 wiw_iwi 的权值。kkk 次询问一个长度为 mmm 的串 TTT 与 SSS ...

字符串

2022-07-28

1 278