标签:概率和期望

AGC007 C – Pushing Balls

huangkui 2018年2月7日 No Comments Problem , , ,

题目链接:传送门 Description 在一条直线上有 n 个球和 n + 1 个坑共 2n + 1 个“物品”,i 个球在第 i 和第i + 1 个坑之间。 球与坑之间是有距离的,这些距离组成了首项为 a,公差为 x 的等差数列。即第i个物品和第 i + 1 个物品之间的距离是 a + (i − 1)x。 小 A 会进行 n 轮操作,每轮操作中,先从剩下的球中等概率地选择一个,然后等概率地选择一个方向,这个球将会朝这个方向滚,直到遇到一个里面 […]

NOIP2016 换教室 期望DP

huangkui 2017年8月17日 No Comments Problem, 未分类 , , ,

题目链接:传送门 Description 有n个时间段,第i个时间段可以选择在ci教室上课,也可以选择申请换课,有ki概率申请通过,在di上课,另外1−ki的概率留在ci教室。 总共有v个教室,e条路径双向联通教室xi和yi,路径有权值wi。在课间时(相邻两个时间段的间隔中),你要从上一个教室走最短路径到下一个教室。 现在你有m次申请机会,只能提前申请一堆换课(也就是你不能在知道某一次申请结果后再去申请下一个换课)。求总距离的最小期望。 1≤n≤ […]

Page 1 of 1