当前位置: 代码迷 >> 综合 >> 百度之星初赛 C hdu 6382 odds
  详细解决方案

百度之星初赛 C hdu 6382 odds

热度:28   发布时间:2023-10-29 05:50:20.0

题意

度度熊有一棵 N 个节点 (node) 的有根树 (rooted tree),树上的每条边 (edge) 都有一个整数的权重,对于每一个非叶的节点 (non-leaf node),通往子节点 (child) 的所有边的权重总和为 2×105。
考虑以下在树上行走的随机过程:
1. 起始位置在根节点。
2. 如果现在位置在任何一个叶节点 (leaf node) 上,则结束。
3. 令现在所在的节点通往子节点i的边为 ei,其权重为 vi。
4. 定义 P(ei) 为选择到边 ei 的概率,以 P(ei)=vi/(2×105) 的概率分布随机选择一条边,移动至对应的子节点。
5. 跳至第 2. 步骤。
接下来我们定义以下的操作:
1. 选定一个非叶节点
2. 将这个节点所有通往子节点的边的权重随意重新排序,亦即可以无限次地交换彼此之间的权重,但不能改变权重的大小。
给定一个固定的 X 值,请对于每个叶节点分开考虑以下问题:
如果能进行至多 X 次的操作,那到达这个叶节点的概率最大可以多大呢?

题解

说一下做法吧
维护一个multiset
维护一下他到根换之后代价的改变的大小
只维护前k大
如果有新的,就替换最小的
然后回溯的时候还原就可以了
注意一下各种0的情况就好了

代码

我还没A,就不贴出来了。。