2024/10/21

CF213E Two Permutations

考虑枚举 \(x\)，我们每次就只考虑值在 \([1+x,n+x]\) 的数单独拿出来，看他们是否与 \(a_i+x\) 相同即可。

具体实现时，我们可以通过一棵平衡树来快速插入和删除一个数，并用 Hash 来维护序列信息。

CF961F k-substrings

串的中心不会改变，所以答案总的改变量不会超过 \(2n\)，每次用 Hash 暴力维护即可。

CF580E Kefa and Watch

直接用 char 的内置函数，跑的飞快。

CF504E Misha and LCP on Tree

一个显然的做法就是枚举两条路径的前缀长度，然后 Hash 判断是否相同。

但 Hash 不好维护，所以可以做一次树剖，然后判断每一条重链上的 Hash 值是否相同，若相同就继续跳重链，否则就直接在重链上二分。

可以做到 \(O(m\log n)\)。

Cerc2016 Appearance Analysis

模拟，用 Hash 维护四个方向。

Sdoi2015 双旋转字符串

只考虑 \(n\ge m\) 的情况，若 \(n<m\) 直接交换就行了。

那么拼接过后的字符串后面的一段的前缀，一定是 \(S\) 中字符串一段长度为 \(n-\frac{n+m}{2}\) 的后缀。

所以我们可以枚举 \(S\) 中每一个旋转得到的字符串，将多余一段加到 map 里。直接用 \(T\) 中的字符串来统计答案。