Difference between revisions of "XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea"
Jump to navigation
Jump to search
(Created page with "这场没罚时的。 == Problem A == Solved by zerol. 02:43 (+) == Problem C == Solved by ultmaster. 02:57 (+4) == Problem D == Solved by kblack. 03:29 (+13) == Proble...") |
|||
Line 8: | Line 8: | ||
Solved by ultmaster. 02:57 (+4) | Solved by ultmaster. 02:57 (+4) | ||
+ | |||
+ | 题意:A 到 B 有很多桥,每座桥上有若干个点。一座桥上只要有一个点挂了,整座桥就挂了。每个点有一定概率会挂,现在要求用最少的期望次数检测 A 到 B 之间有无通路。 | ||
+ | |||
+ | 题解: | ||
+ | |||
+ | * 首先计算每座桥挂了的概率:$s_i$。 | ||
+ | * 其次计算检测第 $i$ 座桥需要的时间:$t_i$(把点按照挂的概率从高到低排个序,然后用期望公式依次算过去就好)。 | ||
+ | * 最后答案等于 $f_i = s_i f_{i+1} + t_i$。我们要找某个排列使得 $f_1$ 最小。你要相信这个东西排个序贪心一下就好了,于是列一个 $n=2$ 的方程解一解。 | ||
+ | * 很怀疑精度不行,正准备把乘法改成 log 加,突然就过了。 | ||
== Problem D == | == Problem D == |
Revision as of 16:30, 22 March 2019
这场没罚时的。
Problem A
Solved by zerol. 02:43 (+)
Problem C
Solved by ultmaster. 02:57 (+4)
题意:A 到 B 有很多桥,每座桥上有若干个点。一座桥上只要有一个点挂了,整座桥就挂了。每个点有一定概率会挂,现在要求用最少的期望次数检测 A 到 B 之间有无通路。
题解:
- 首先计算每座桥挂了的概率:$s_i$。
- 其次计算检测第 $i$ 座桥需要的时间:$t_i$(把点按照挂的概率从高到低排个序,然后用期望公式依次算过去就好)。
- 最后答案等于 $f_i = s_i f_{i+1} + t_i$。我们要找某个排列使得 $f_1$ 最小。你要相信这个东西排个序贪心一下就好了,于是列一个 $n=2$ 的方程解一解。
- 很怀疑精度不行,正准备把乘法改成 log 加,突然就过了。
Problem D
Solved by kblack. 03:29 (+13)
Problem F
Solved by zerol. 04:53 (+8)
Problem L
Unsolved. (-3)