P3586 [POI2015] LOG 题解

问题可以转化为一个 $x \times y$ 的矩阵，有 $n$ 种宽高 $1$，个数 $a_i<y$ 的方块， 问他们不重合放置，能完全覆盖矩阵且矩阵每一行方块类型都不同的条件。

先说结论。 当：

成立。

证明可以考虑构造。

首先要说明第一轮一定可以完成，易证。

若按行从下往上搭建，设每一轮填满一行，若在第 $k$ 轮时有 $num$ 个高度等于 $y-k+1$ 的数，如果 $num>=x$ 直接都填这些就行。否则优先使用他们，这让高度不仅没有浪费还减短了矩阵宽度。本轮剩下的可以直接乱填，可以证明在高度没有损耗的前提下能完成本轮。然后直接到下一轮。由于现在这种情况下下一轮的情况和本轮一致，直接循环填就可以了。