题解 CF1320D 【Reachable Strings】

· · 题解

提供一个差不多的解法。

注意到操作是可逆的，所以我们只要找到一个等价类让两者相等，两者就一定相等。

所以我们就可以找到等价类中字典序最小的串进行比较，那么只需要执行 110\rightarrow 011 这个操作。

可以发现，11 这种串一定可以移到串的末尾，而且移到末尾可以视为删除 11。

接下来就可以用线段树维护左右边界的数，目前的长度，哈希的值，在上传的时候把 11 删掉。

时间 \mathcal{O}(n\log n)。

代码使用了双哈希，所以比较慢。

code