题解:AT_arc192_a [ARC192A] ARC Arc

· · 题解

把串串写出来(这里写一部分) \texttt{ARCRARCRARC}

若初始 01 串全都为 0,当且仅当长度为 4 的倍数的时候合法。

剩下的情况至少有一个 1,那么我们要处理的就是被 1 分割开的极长 0 段。

对于极长 0 段,若其长度为偶数,以当前末尾的 1 为 C 或 A 向前扩展偶数长度即可,对两端的 1 取值并没有影响。若长度为奇数,这时以当前末尾的 1 为 C 或 A 向前扩展奇数长度,会对极长 0 段另一端的 1 的取值造成影响,其实是限制这两个 1 的取值相同或不同,所以使用扩展域并查集判断是否出环就好了。

code