首页 > Antenna Placement
开通博客写题解
头像 吃花椒的妙酱
发表于 2021-08-02 22:33:18
题目大意：给定棋盘，棋盘上有若干个被删除的点，现在有1*2多米诺骨牌，求至少多少张将棋盘全覆盖（可越界可重叠）（这题是这题的升级版 思路：二分图匹配 对于多米诺骨牌来说，它有两个点。我们将一张骨牌拆成两个点，再将棋盘黑白染色，不难发现，两个点的颜色一定不同，至此可以建图了，一个棋盘可以这样染色 10 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 回归梦想
发表于 2021-01-14 00:01:49
问题： n * m的矩阵，有一些障碍点，用12的骨牌覆盖所有非障碍点 (12骨牌可重叠，骨牌可越界，骨牌可延伸到障碍点) 问最少需要 多少个。 题解： • 尽量用一个骨牌覆盖两个格子，覆盖不了了再重叠使用骨牌• 用和上一个题一样的方式求一个最大匹配，那么就有（2 * 最大匹配）个点已经被覆盖了• 剩 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”