Difference between revisions of "Training 2: Probability and Expectation"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 10: | Line 10: | ||
Solved by Kilo_5723 && Weaver_zhu. | Solved by Kilo_5723 && Weaver_zhu. | ||
| + | |||
| + | 题意：两个人在一个无向联通图的两点上，每个人在第 $i$ 个点上有 $p_i$ 的概率留在原点，有 $1-p_i$ 的概率从所有连边中随机选择一条出边去别的房间。每一个时刻，两人按如上规则随机移动，求两个人第一次选择去同一个房间时，这个房间是每个房间的概率。 | ||
| + | |||
| + | 题解：将两个人各自所在房间的二元组 $(a,b)$ 设为一个状态，将每个状态到达每个终态 $a=b$ 的概率设为未知量，对每一个二元组可能到达的二元组状态列出方程，高斯消元求解即可。 | ||
== Problem C == | == Problem C == | ||
Revision as of 15:18, 8 May 2019
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.
Problem D
Solved by Kilo_5723.
Problem E
Solved by Kilo_5723.
Problem F
Solved by Kilo_5723.
Problem G
Solved by Kilo_5723.
Problem H
Solved by Kilo_5723.