AGC011D Half Reflector

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

题意：有一排 个机器，每个机器为两种状态之一 ：

  • : 反弹滚过来的球。
  • : 允许球通过。

每与球互动一次，机器的状态就会改变。

现在从左侧投入一个球，等待直到球从左侧或者右侧离开。可以证明球一定会离开。

重复投 次，问最终机器的状态。

，，时限 。

好毒啊，脑补要累死啦……写个暴力观察一下规律。

可以发现，从左侧投入一个球时，机器的改变分为两种情况 ：

  • 最左侧是 ：最左侧变为 。

  • 最左侧不是 ：整个序列取反后，向左循环移位一次。

不难写出一个 的模拟。

继续观察规律，当不断投球时， 形如 ...BABA 的后缀不会被改变。

最终会稳定在 BABABA 或者 xBABA（第一位反复横跳）

而且，每投至多两次球，必然会在后方多产生一组 BA。

所以我们只需模拟 轮，之后的行为是容易预测的。