AGC019D Shift and Flip

发表于 分类于 ， ， 阅读次数：

题意：给出两个长度为 的 串 。

可以进行下列两种操作：

  • 将 循环移位（左移或右移）一次。

  • 对某个 的 ，将 取反。

问使 与 相等至少需要几次操作，或指出无解。

，时限 。

显然 全 是无解的充要条件。

首先枚举最终 转过几轮，然后 中需要使用操作二的位置就能够确定了。

不妨将需要修改的位置设为 ，不需要的设为 。

先思考如何修改这些位置，相当于：将 适当地旋转，使得 的每个 都被某个 的 “擦过”。

不难发现， 的旋转最多只会回一次头。

每个 中的 分别向左向右查看 中最近的 ，假设距离分别为 ，则 右移达到 或者左移达到 。（注意要反过来）

若最终左移 右移 ，则移动步数为 ，因为需要回头。

接下来考虑移动到给定位移 的消耗。

不妨先向左，再向右，然后移到 （右起）。保证 。

代价为 。

先向右再向左可以简单地将串反转再求一次。

考虑如何选定合适的 。

首先把 的点都丢掉。

接下来，问题就变成了：有 个约束，形为： 或者 。

要求找出一对 满足所有约束，且和最小。

将所有约束按照 排序，枚举 就能满足一个前缀，剩下的后缀 最大值就是 。

使用桶排序即可做到 。