ARC 172A

贪心，可以证明优先剪出更大的块是一定不劣的。

填空：给定一张长 $7$ 宽 $11$ 的纸片，我们不可能剪出

• 总面积大于 ?? 的边长至少为 $1$ 的正方形纸片
• 总面积大于 ?? 的边长至少为 $2$ 的正方形纸片
• 总面积大于 ?? 的边长至少为 $4$ 的正方形纸片

提示一的答案：$77$，$60$，$32$。

考虑将提示三的结论一般化，并证明当上述所有条件都不满足时一定有解。

对于一个长 $h$ 宽 $w$ 的矩形纸片，可以满足所有的需求当且仅当如下条件均不成立：

• 边长至少为 $1$ 的正方形纸片总面积大于 $h\times w$；
• 边长至少为 $2$ 的正方形纸片总面积大于 $2\lfloor {\displaystyle \frac{h}{2}}\rfloor \times 2\lfloor {\displaystyle \frac{w}{2}}\rfloor$；
• 边长至少为 $4$ 的正方形纸片总面积大于 $4\lfloor {\displaystyle \frac{h}{4}}\rfloor \times 4\lfloor {\displaystyle \frac{w}{4}}\rfloor$；
• 以此类推，边长至少为 $2^k$ 的正方形纸片总面积大于 $2^k\lfloor {\displaystyle \frac{h}{2^k}}\rfloor \times 2^k\lfloor {\displaystyle \frac{w}{2^k}}\rfloor$。

证明：$\Leftarrow$：考虑反证，该结论是显然的。

$\Rightarrow$：考虑贪心，优先满足大正方形的需求，留下的边角料供小正方形使用。由于边长一定为 $2$ 的幂次，可以证明对于划给长度至少为 $2^k$ 的正方形使用的区域一定可以完美划分成一系列边长为 $2^k$ 的正方形格子（这句话可能有点难以理解，可以考虑一个反例，用 $27\times 27$ 的纸片剪出 $3\times 3$ 与 $2\times 2$ 的正方形，此时可能会产生即使需求的总面积小于 ${27}^2$ 也无法满足的情况，因为即使按照最优的方法剪纸仍然可能产生一系列无法利用的边角料），因此一定可以证明当能够满足所有的需求时，上述的每一个条件都不成立。如下图所示：

依照上面的结论统计即可。时间复杂度 $\mathcal{O}(n)$。