5.22 字符串专题模拟赛

T1 P7469 [NOI Online 2021 提高组] 积木小赛

签到题，考虑固定 \(\texttt{Bob}\) 的左端点，双指针去判断是否匹配即可，时间复杂度 \(O(n^2)\)。

T2 P7114 [NOIP2020] 字符串匹配

考虑到 \(AB\) 必然是一个前缀，枚举 \(AB\) 长度 \(len\)，\(C\) 的长度只有 \(\lfloor\dfrac{n-len}{len}\rfloor\)。

考虑枚举 \(C\) 的长度，用树状数组维护可以做到 \(O(n\log n\log |\sum|)\)，\(|\sum|\) 为字符集大小。

把树状数组换成暴力，可以做到 \(O(n\log n+n|\sum|)\)，实现好可以通过。

submission。

T3 P7717 「EZEC-10」序列

把图建出来，对于一个连通块，令其中一个点为 \(x\)。

问题转化为数 \(x\) 的个数，使得其满足条件：

这个可以用 \(\texttt{01Trie}\) 上 dfs 解决，时间复杂度 \(O(n\log V)\)，\(V\) 为值域。

代码稍后补。

T4 P5353 树上后缀排序

场上的另一个签到题。

直接默写一个后缀排序的板子上去，稍微改改就过了，很快啊！

时间复杂度显然是 \(O(n\log n)\)。

submission。