题解：P14474 拼积木

· · 题解

题外话：如果空格太多的话，答案下界会达到 n^3 级别：考虑初始状态是左边一半铺满右边一半空，最终状态是右边一半铺满左边一半空，我们一次操作只会移动空格 O(1) 距离，而所有空位移动的总距离是 O(n^3)。所以问题限制了空格数 \le 500 （n/2 级别）

解法如下。首先，我们把状态理解为一个网格图（同时是二分图），每个积木对应一条边。则一个状态是一个匹配边集。求初始状态和最终状态的对称差图，由于匹配中每个点度数 \le 1，对称差图每个点度数一定 \le 2。所以图上只可能有四种联通块：

  1. 交替环
  2. 偶交替路
  3. 奇交替路（初始状态边多）
  4. 奇交替路（最终状态边多）

首先，我们可以通过一次操作让对称差图上一条交替路长度减 2（对于“奇交替路（最终状态边多）”这种情况需要去操作目标图倒着移动。移动可逆，所以先用栈记录下来这种移动，实际操作时最后倒着移回去就行。）。所以先通过 \le n^2/2 次操作消除所有的偶交替路并将所有奇交替路长度减到 1 条边。（1 条边的交替路相当于扣掉/加上一整块积木）

然后我们把对称差图上剩下的长为 1 的奇交替路（其实就是 1\times 2 的空格位置）随意配对。这样，我们需要交换一块 1\times 2 的积木和一个 1\times 2 的空格的位置。我们可以按任意一个曼哈顿距离最短的路线移动，每次交换一块积木和相邻位置的一个 1\times 2 空格，每移一格均摊最多操作 2 次。（注意有可能有跨过中间很多个空格的情况，需要特殊处理之后第一个碰到的积木移动）总移动次数 \le S/2 \times 2 \times 2n（S 为总空格数）。问题输入限制总空格数 \le n/2 之后是 \le n^2。

然后就只剩交替环了。这部分套用原来的题（P5372 [SNOI2019] 积木）的做法即可。记得每个积木连通块分别处理。这部分 \le 2n^2

总共操作次数 \le 3.5 n^2