Trie

中规中矩的一场模拟赛。

T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。

T2 有我喜欢的马拉车 Manacher 算法，是印象里第二次在模拟赛应用。

然后就没时间了。后两题仍然只有暴力分，但最近频繁遇到跟凸包和线性函数相关的题目，这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题，但思路是错误的。

简略题解

A – 石蒜反冲

这好像是很早以前的译名了。现在它叫《莉可丽丝》。

遇见多模式串匹配，自然想到自动机上 DP。但我们发现题目中给定的两个串 sakana chinanago 在任何一个文本串中最多只能匹配其中一个，且匹配位置唯一。于是简单计数 DP 转移，记录当前二者匹配数之差与目前匹配位置即可。

一些不应用就过不了的优化：

• 二者数量之差可只记录到 $\frac{n}{15}$。$15$ 是两个串的总长度。
• 转移时对于 ? s c a o 还有其他字符分类讨论，保证单次转移复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(1)$。

时间复杂度 $\bigO(n^2)$。 （更多…）