题解：AT_awtf2024_e Colorful Stamps

yueason · 2024-08-12 18:03:17 · 题解

让我们把压印操作重新措辞如下:

• 最初，所有单元格都未使用。按下戳记 (h,w) 时，选择仅由未使用的单元格组成的 h \times w 矩形。然后，在矩形中选择一个单元格，并将其标记为已使用。

邮票 (h,w) 的颜色保持不变的单元格对应于标记为已使用的单元格。目标是对所有邮票执行此操作。

让我们考虑一个有效操作序列的属性。

总之，以下属性具有:

• 财产 1 : 在业务的所有阶段，该地区都满足以下两个条件:

• 对于每个 i ， i -第五行中未使用的单元格的列号形成一个区间 [l_i, r_i] (该区间可能为空)。如果这些间隔被适当地重新排列， [l_{i_1}, r_{i_1}] \subseteq [l_{i_2}, r_{i_2}] \subseteq \cdots \subseteq [l_{i_N}, r_{i_N}] 。

• 对于每个 j ， j -th 列中未使用的单元格的行号形成一个区间 [u_j, d_j] (该区间可能为空)。如果这些间隔被适当地重新排列， [u_{j_1}, d_{j_1}] \subseteq [u_{j_2}, d_{j_2}] \subseteq \cdots \subseteq [u_{j_N}, d_{j_N}] 。 属性 2 : 当且仅当大小 (h,w) 的戳记未使用时，才可以在未使用区域内获取大小为 (h,w) 的矩形。

我们将用归纳法来证明这些性质，很明显，它们在初始状态是成立的。

考虑按下来自任意状态的戳记。首先，要压印的邮票的尺寸必须是最大的。假设按下了非最大戳记并且使用的单元格为 (x,y) 。然后，考虑到包含单元格 (x,y) 的最大矩形，将不再可能使用与此矩形相同大小的戳记。这不会导致有效的操作序列，因此要按下的戳记的大小必须始终是最大的。

出于同样的原因，也不可能使用包含在两个或多个最大矩形中的单元格。

此外，不能使用矩形的四个角以外的单元格。考虑以下状态(其中’。表示使用过的单元格)。假设我们要在左上角 4 \times 5 矩形上按一个戳记。

如果使用单元格 A ( =(4,4) )会发生什么情况？使用大小为 4 \times 4 的戳记将不再可能，因此此操作无效。一般来说，我们看到除了四个角之外的单元格不能使用。

相反，如果我们使用的单元格恰好包含在一个最大矩形中，并且对应于四个角中的一个，那么它总是有效的吗？事实上，它将是有效的。如果使用满足上述条件的单元格，剩余的未使用单元格将满足最初提出的所有条件。

让我们回到最初的问题。对于已经按下的 K 邮票，我们需要适当地确定使用了四个角中的哪一个，以确保满足上述条件。

假设在位置 (a,b) 处按下邮票 (h,w) ，并使用单元格 (x,y) ( x=a 或 a+h-1 ，以及 y=b 或 b+w-1 )。若要获得有效操作， (x,y) 必须满足以下条件:

• 在压制 K 邮票的阶段，单元格 (x,y) 不被另一个邮票着色。
• 在按压戳记 (h,w) 之前，使用单元格 (x,b-1) 、 (x,b+w) 、 (a-1,y) 和 (a+h,y) 。在这里，细胞是出了董事会被认为是使用。

我们将使用布尔变量表示 x=a 和 x=a+h-1 之间的选择。类似地，在 y=b 和 y=b+w-1 之间的选择也将用布尔变量表示。

然后，所有的条件都可以写成2-SAT 的形式，这样，我们就可以解决这个问题了。

让我们分析一下计算的复杂性。2-SAT 中变量和约束的个数为 O(K) ，因此该部分的复杂度为 O(N^2) 。但是，我们需要在按下初始的 K 邮票(需要 O(N^3) (或任何可行的复杂性))之后确定板状态。因此，最终的复杂度是 O(N^3)。