自动搬运

查看原文

来自洛谷，原作者为

	iostream Think three times, code twice and take the first place.

搬运于2025-08-24 22:20:29，当前版本为作者最后更新于2020-04-18 10:32:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

是一个省选算法强行三合一的题？

Problem 1：

显然对棋盘黑白染色之后求一个二分图最大匹配即可。

$O((nm)^{1.5})$

Problem 2：

注意到题目条件有 $n,m=2^t,K=1$ 那么这个东西肯定是可以尽可能装满的，故答案是 $\lfloor {nm-1\over 3} \rfloor$ ，但是由于 $n,m$ 巨大，这里要用 NTT 算一下高精度乘法。。。

$O(\log n\log \log n)$

Problem 3：

$n,m\le 11$ 那么直接插头 dp 即可，具体实现的时候可以状压轮廓线然后枚举格子转移，根据骨牌的特点，需要记录两行轮廓线。

$O(nm2^{2n})$