题解：CF2068I Pinball

· · 题解

一种不同于官解的更适合人类的正向思考方式。

经过读题，可以发现：

  1. 斜墙可以拆。
  2. 块状墙不能拆。
  3. 在不拆墙的情况下，球总是会来回弹。

其中，来回弹指球在一个环路上（很可能退化成在路径上往复运动）绕。

于是我们考虑将每两个格子时间建出两个点对应两个方向。

于是我们发现只有两类环路，分别命名为 A 类环和 B 类环。

A 类环：不经过块状墙的环，将反过来也是一个 A 类环，称之为这个 A 类环的反环，将这个环与其反环称为一组 A 类环。

B 类环：经过两个块状墙的环。

容易发现只有这两类环。

考虑拆斜墙的影响。

  1. 斜墙在同一（组）环上。
  2. 斜墙影响两组 A 类环，会拼接为一组 A 类环；
  3. 斜墙影响两个 B 类环，会拼接为一个 B 类环；
  4. 斜墙影响一组 A 类环和一个 B 类环，会拼接为一个 B 类环。

对于第 1 类，拆墙一定不优，不拆。

显然对于第 3,4 类，拆墙之后会拼接为一个 B 类环，所以无论原先哪个环可达，拼接后一定全部可达。

于是考虑第 2 类，显然拼接后球在这一组环上的方向由原先可达的环的方向确定。

于是将一组 A 类环作为整体考虑。

发现一旦有 B 类环参与，就会拼接为 B 类环，所以如果拼接为 A 类环，一定没有 B 类环参与。

所以拼接过程中任何一个 A 类环的方向只有初始决定，而初始球可以在正反两个方向中任选，所以拼接出的 A 类环组方向一定任选。

所以我们现在将一个 B 类环和一组 A 类环作为一个点考虑，若两个环共有斜墙就连边，显然我们可以通过 k 次操作达到 任意一个距离不大于 k 的所有环（组） 中的任意点。

此外，我们只有使用不小于 k 次才能达到距离为 k 的环（组）中的所有点。

于是可以证明，对于点，记它所在环（组）到初始环（组）的距离为 k，我们可以用最优策略在 k 次拆墙的操作中达到该点。

然后依旧简单的 01 bfs。

本篇的思路似乎正常一点？