mengbierr

一个蒟蒻的博客

4月19

BZOJ5288&luogu4436&LOJ2508 : [Hnoi2018]游戏

正解跑不过暴力…
暴力拓展的问题在于一个位置会拓展多次。
对于一扇门,如果它的钥匙在门的一边,则人永远不能从另一边走到钥匙这边,所以可以把没有门分隔的点看成一个点,对于一扇门位置在x,若钥匙在x左边,则x+1向x连边,否则相反。按拓扑序不断拓展,这样一个位置就只会拓展一次了。

发表评论

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