2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest

From EOJ Wiki
Revision as of 06:48, 16 November 2018 by Kblack (talk | contribs) (→‎Problem D)
Jump to navigation Jump to search

Problem A

Solved by zerol. 00:32 (+1)

温暖的签到。但是我把 m 打成 n 了。。。

Problem B

Solved by ultmaster. 03:48 (+)

题意:在树上装两盏半径为 $r$ 的路灯,要求覆盖整棵树。求最小的 $r$。

题解:我们大概可以猜出这两盏路灯一定装在直径的第 $r$ 个点,和倒数第 $r$ 个点上。二分答案判一判就好了。

Problem D

Solved by kblack. 03:23 (+1)

题意:$ n \times m $ 的棋盘,每次挑一个空的放上棋子,问期望多久后所有行列都有棋子。

题解:设计状态 dp[r][c][x] 表示现在占领了 r 行 c 列,且交点中还有 x 个空的,然后按新开行列否分四种情况转移就行了。

明明是原题再现,结果制造了不存在的问题,自我枪毙,拖着队友走向自闭。容斥的精度真的不太行。

Problem E

Unsolved. (-1)

Problem H

Solved by kblack. 02:56 (+1)

Problem I

Solved by kblack. 00:34 (+)

Problem K

Solved by kblack. 00:20 (+)