这里会显示出您选择的修订版和当前版本之间的差别。
后一修订版 | 前一修订版 | ||
2020-2021:teams:looking_up_at_the_starry_sky:百度之星初赛一_1007 [2020/07/24 17:19] x342333349 创建 |
2020-2021:teams:looking_up_at_the_starry_sky:百度之星初赛一_1007 [2020/07/24 17:40] (当前版本) x342333349 [简单题解] |
||
---|---|---|---|
行 1: | 行 1: | ||
[[http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=889&pid=1007|题面]] | [[http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=889&pid=1007|题面]] | ||
+ | |||
+ | ====简单题意==== | ||
+ | |||
+ | 房间是个 $n\times m$ 的网格,一共有 $k$ 个窗户,都在上下左右四条边上。在第 $0$ 时刻,每个窗户对应的格子上都会出现若干只蚊子。 | ||
+ | \\ | ||
+ | 蚊子每个时刻可以往上下左右移动一格或者呆在原地不动。 | ||
+ | \\ | ||
+ | 假设这些蚊子都足够聪明,请问最少花费多少时刻,使得所有格子上都有至少一只蚊子? | ||
+ | \\ | ||
+ | 蚊子在第 $0$ 时刻不能动。 | ||
+ | \\ | ||
+ | $n,m,k(1\leq n,m\leq 1000,1≤k≤6)$ | ||
+ | |||
+ | ====简单题解==== | ||
+ | 二分答案,把每个点映射到对应的 $2^k$ 状态节点中(容量$+1$),每个窗格往对应可达状态节点($\text{该位}=1$)连边,网络流检验答案合法性。 | ||
+ | |||
+ | @ws_zzyer 表示可以用霍尔定理替代网络流检验答案,待尝试! |