补充题解
查看原帖
补充题解
174045
FZzzz楼主2022/9/27 16:43

为啥边只连同色点就说明两种颜色不互相影响呢?仔细想一想,我们是不是还有一个这样的限制:同一个骨牌对应的两条边,它们是不同色的,但是不能同时被使用。

我们把白色空格走的路径和黑色空格走的路径这个二元组叫做方案。如果一个方案没有同时使用这样的两条边,那么它肯定是合法的。但是对于不满足这个限制的方案呢?官方题解讨论了这种情况。

具体来说,假设一个方案中,白色空格走某条路径到达 u1u_1,黑色空格走某条路径到达 u2u_2,并且它们分别经过了同一个骨牌对应的两条边。

假设走了这两条边以后分别到达 v1v_1v2v_2,那么它们一定是这个骨牌覆盖的两个点。那么,我们直接方案中它们之前的点都去掉,也就是说直接把最开始去掉的骨牌改成 v1v_1v2v_2

这样会得到一个新的方案,并且它的两条路径的长度和会减少。通过归纳我们就知道一定存在一个没有同时使用一个骨牌对应的两条边的方案,它最后走到的两个点也是 u1u_1u2u_2

所以我们可以直接不用考虑这个限制。

2022/9/27 16:43
加载中...