自动搬运

查看原文

来自洛谷，原作者为

	Felix72 公式和原理永远无法推论人情。

搬运于2025-08-24 21:45:48，当前版本为作者最后更新于2025-05-04 22:54:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题号这么小的黑题还没有题解，我给完善一下。

一个想法是枚举三块拼图和他们的旋转角度、是否翻转以及坐标，这样的复杂度是 $O(K^3N^4)$ 的（忽略枚举方向的 $8$ 倍常数）。

要优化这个算法，我们有以下方法：

• 定义一块拼图的左上坐标为其最左边的有颜色的单元格坐标，若有多个取最上面的坐标。若已知原拼图的左上坐标来自第 $i$ 块拼图，则该位置来自第 $i$ 块拼图的左上坐标；
• 使用哈希快速判断两块拼图是否相等。

第一个优化使得枚举前两块拼图时无需枚举其位置，第二个优化使得枚举第三块拼图时可以 $O(1)$ 判断，时间复杂度来到 $O(K^2N^2)$。

如果 $R, C$ 如题面说的一样在 $100$ 之内，那这个复杂度确实是能过的（$100^4 = 10^8$），但是数据中 $R, C$ 好像和 $N, M$ 一个量级，再加上 $8$ 倍常数的影响，肯定是无法通过的。这时需要一些剪枝：

• 枚举所有的 $x, y, z$，先判断一下这三块拼图是否在颜色个数和上和原拼图相等，这样可以筛出一些二元组 $(i, j)$，保证 $i, j$ 同时存在的拼法一定非法。这样 $O(K ^ 2)$ 就跑不满了；
• 对一块拼图，先枚举其 $8$ 中不同的方向，如果其中有相同的，后面就不枚举它，这样 $8$ 倍常数也跑不满；
• 对一块拼图，先计算出其左上坐标，判合法的时候就无需再算一次了，这样 $O(N^2)$ 带的常数变小。

这三个剪枝不容易同时卡掉至少两个（或者说数据没卡），可以通过。