【题解】CF1268B Domino for Young

破壁人五号 · 2021-11-05 21:29:35 · 题解

题目链接

这篇题解重点讲述结论的证明。

首先考察第一个结论：如果一个杨表黑白染色后两种颜色的数量相等，那么其可以被多米诺骨牌密铺。

这个结论的正确性没有那么显然，洛谷上已有题解的证明似乎都没有用到杨表的性质；这样的证明都是错误的，因为如果不要求图是杨表，我们有如下反例：

该图无法用骨牌密铺，但它的黑白格子数量相等。

该结论的正确证明如下：从一个黑白染色后两种颜色的数量相等的杨表出发：

• 如果该杨表有两行长度相同、或两列高度相同，则我们可以填上一个骨牌使剩下的部分仍是杨表，且黑白格子数仍然相同（如下方左图）；
• 如果没有，那么杨表形状如下方右图，其黑白颜色格子数一定不同，矛盾；
• 那么一个杨表一定能被填满。

接着考虑当黑白格子个数不等时怎么做。我们考虑模仿上述过程，当没有两行长度相同或两列高度相同时，我们去掉最上方那个格子（其颜色一定是出现次数较多的一种）之后继续做，显然全程只会把出现较多的格子留空。

于是答案为两种颜色格子数之最小值的结论得证。