Training 2: Probability and Expectation

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by Kilo_5723 && Weaver_zhu.

题意:给定一个无向联通图,每一条边有一个权值,从起点开始每次随机选一条边走,问走到终点时,走过的所有边权值异或和的期望值。

题解:对于边权的每一个二进制位分别求解,将每个点到终点路径异或和的期望值设为未知数,对每一个点及其所有出边列出方程,高斯消元求解即可。

Problem B

Solved by Kilo_5723 && Weaver_zhu.

题意:两个人在一个无向联通图的两点上,每个人在第 $i$ 个点上有 $p_i$ 的概率留在原点,有 $1-p_i$ 的概率从所有连边中随机选择一条出边去别的房间。每一个时刻,两人按如上规则随机移动,求两个人第一次选择去同一个房间时,这个房间是每个房间的概率。

题解:将两个人各自所在房间的二元组 $(a,b)$ 设为一个状态,将每个状态到达每个终态 $a=b$ 的概率设为未知量,对每一个二元组可能到达的二元组状态列出方程,高斯消元求解即可。

Problem C

Solved by Kilo_5723.

题意:你的生命值是 $p$,最大生命值是 $n$,每一次恢复一点生命值,随后有 $m$ 轮攻击,每轮攻击有 $frac{1}{p}$ 的概率对你造成 $1$ 点伤害。问你在被打死之前回复生命值的期望值。

题解:将每个生命值被打死之前回复生命值的期望值设为未知量,将每个血量可能到达的状态列出方程。我们发现,生命值为 $p$ 时最多可能达到 $p+1$,也就是这个矩阵已经非常接近上三角矩阵了,只要用每一行消去下一行的元就可以了。我们只需要求出一个未知量的值,那么用它下面的每一行消这一行的元就可以了,整体复杂度是 $O(n^2)$ 的。

Problem D

Solved by Kilo_5723.

题意:$n$ 次操作,第 $i$ 次操作有 $p_i$ 的概率成功。最后的得分是每一段极长的连续成功操作串的长度的三次方和,求最后得分的期望值。

题解:对于任意一个从 $i$ 到 $j$ 的极长连续成功操作串,它对答案的贡献是 $(1-p_{i-1}) \times \prod_{k=i}^{j} p_k \times (1-p_{j+1}) \times (j-i+1)^3$

Problem E

Solved by Kilo_5723.

Problem F

Solved by Kilo_5723.

Problem G

Solved by Kilo_5723.

Problem H

Solved by Kilo_5723.