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\) 中的字符串来统计答案。