题解 P6407 【[SDOI2012] 棋盘覆盖】
iostream
·
·
题解
是一个省选算法强行三合一的题？
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：
$O(nm2^{2n})