比赛链接:https://vjudge.net/contest/404866

B – Chessboard

首先可以发现最后一个上色的块一定在四个角上。接着考虑倒着推,根据题目的要求发现每次必须把一行或者一列上的色块全部上满色。把操作顺序反过来后,如果给某一行上色时留下一部分不上色,那么后续将这一部分补上颜色时一定会与题意矛盾。

考虑从四个角的任意一个开始,有 $n-1$ 行 $m-1$ 列需要上色,每次上色可以在行和列中选一个上色,因此有 $4 \cdot {n+m-2 \choose n-1}$ 种方案

行数或列数为 $1$ 的情况需要特判。

代码链接

H – Prince and Princess

不难发现,如果说真话的人数超过一半,则一定可以找到公主的位置,否则有可能无法确定公主的位置。

要特判只有一间房子的情况,比赛时忘了特判卡了很久。

代码链接

I – Space Station

考虑记忆化搜索,搜索的情况数的上限是 $50$ 以内的无序拆分数之和。

当目前的能量值大于 $50$ 时可以直接剪枝,然后还是 TLE。考虑能量为 $0$ 的星球可以任意时候到达且不影响当前能量,搜索时也可以剪枝。

代码链接

J – Spy

比赛时发现这题可以转化为求二分图的最大权完美匹配,遂复制粘贴一波费用流板子,然后 TLE。然后想到了没有学过的 KM 算法,在网上找了几个 KM 板子复制粘贴一波,然后还是 TLE。打算以后真正学 KM 算法的时候再把这题补完。

发表评论

邮箱地址不会被公开。 必填项已用*标注