Mayflyyh
Mayflyyh
MayFlyyh's Blog

期望
文章归档

POJ 3156 Interconnect

现在有n个点,给你m条边,每次随机选2个点连边(可能选已经连过的)并且花费1个代价,求使n点联通的期望最小代价。 本题关心每个联通块的规模,但不关心每个联通块具体的点。 然后根据规模记忆化搜索,因为规模无法正常表示成值,所以每次hash一下当前dp的状态,然后…

   1,409   2018-08-11 去围观

BZOJ1426 收集邮票

1426: 收集邮票 Time Limit: 1 Sec Memory Limit: 162 MB Description 有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且 买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由…

   77   2018-07-12 去围观

BZOJ1076 [SCOI2008]奖励关

BZOJ 1076: [SCOI2008]奖励关 Time Limit: 10 Sec Memory Limit: 128 MB Description   你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做…

   73   2018-07-12 去围观

BZOJ1415 [Noi2005]聪聪和可可

BZOJ1415 [Noi2005]聪聪和可可 首先要预处理处当前聪聪在i点,可可在j点的时候聪聪下一步要走到哪里(这我都没想出来。。。 然后就比较简单了,根据套路,这个聪聪在x节点的期望应该是可可在j节点走到各种地方后,聪聪跟上的期望,当然也要算出可可留在原地,聪聪…

   58   2018-07-12 去围观