题解：CF1819B The Butcher

lcfollower · 2025-11-29 12:28:53 · 题解

玩 duel 碰到的题，写 TJ 纪念。

首先考虑到这题不像贪心、DP 之类的，我们直接考虑是否存在结论。

有个结论就是最多只有两个答案。

:::info[证明]{open} 假设有一个 r\times c 的初始矩形。

考虑手玩第一次操作，我们发现第一次操作后丢进盒子的那个矩形要么行为 r，要么列为 c。

也即是这个矩形在所有被丢弃进盒子中的矩形内，要么行数最大，要么列数最大。

我们就能得到可能的最大行数 mxx 和最大列数 mxy。

考虑到总面积 S = \sum\limits_{i = 1}^n x_i \times y_i 是定值，因此最终只可能存在两种初始矩形：

• 长 mxx，宽 \frac{S}{mxx}，且 \frac{S}{mxx} 为整数。

• 长 \frac{S}{mxy}，宽 mxy，且 \frac{S}{mxy} 为整数。

:::

现在我们需要做的就是如何判断一个矩形是否能够被切割为若干的 n 个小矩形。

我们用 check(r ,c) 表示当前 r\times c 的矩形是否能被剩下的矩形切割。

我们找到没用过的矩形中，最大的行数 mxx 和最大的列数 mxy，必须满足 mxx = r 或者 mxy = c，如果不满足就不能一刀切割，返回 false。

然后我们递归处理即可。

返回 true 你手玩会发现当 r = 0 或 c = 0 时返回，然后就没了。

时间复杂度为 \mathcal O(n^2)，做两次，懒得去重的话可以用 set 搞答案。

Submission.

很好理解我就不做解释了。

然后考虑每次找很烦。

我们可以用优先队列搞，按行数或者列数从大到小排序。

对于队头，如果用过，我们直接弹出；否则直接按照上面的判断即可。

时间复杂度为 \mathcal O(n\log n)，可以通过。

Submission.