杂题题解

发布时间 2023-06-11 13:18:07作者: 御坂夏铃

序列变化(exchange)

只要第一位确定,后面的 \(n-1\) 位都是唯一确定的。因为具体是 B 还是 C 只取决于两侧字母是否一样,所以两种变化方案其中一种是另一种每一位取反,要么都合法,要么都不合法。

但变化出的方案可能不能继续变化下去,比如 CCC 变化到 BBB 之后就不能再变化了,但变化到 CCC 就可以。

用最小表示法加哈希可以把判重优化到 \(O(N)\)