题解：P3148 [USACO16OPEN] Bull in a China Shop P

Felix72 · 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) 带的常数变小。

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