Difference between revisions of "2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17)"
Jump to navigation
Jump to search
(Created page with "=== Problem A === Solved by ultmaster. 02:48 (+) === Problem F === Solved by ultmaster & zerol. 03:20 (+13) === Problem G === Solved by kblack. 03:38 (+) === Problem H =...") |
|||
| Line 10: | Line 10: | ||
Solved by kblack. 03:38 (+) | Solved by kblack. 03:38 (+) | ||
| + | |||
| + | 题意：可以主动选择是否丢弃随机的方向的随机游走，问最低代价期望。 | ||
| + | |||
| + | 题解：定义 $a_i$ 为从位置 $i$ 到 $n$ 的期望代价，$a_i = \frac{\sum_{(i, j) \in E} min(a_j, a_i)}{d_i} +1 $，如果没有这个min，那这题就只能高斯消元解方程组才能得到答案。因为有这个 min，如果从小到大计算 $a_i$，方程就可以简化，步骤类似 Dijkstra 的松弛，从 $n$ 开始，通过方程已经计算的值，假设剩余未计算的都大于 $a_i$ 去估计 $a_i$，最小的一定是真的答案（发现选用大的一定不会让答案变得更小），set 维护即可。注意原图可能并不联通，可能影响迭代边界。 | ||
=== Problem H === | === Problem H === | ||
Revision as of 02:20, 12 April 2018
Problem A
Solved by ultmaster. 02:48 (+)
Problem F
Solved by ultmaster & zerol. 03:20 (+13)
Problem G
Solved by kblack. 03:38 (+)
题意：可以主动选择是否丢弃随机的方向的随机游走，问最低代价期望。
题解：定义 $a_i$ 为从位置 $i$ 到 $n$ 的期望代价，$a_i = \frac{\sum_{(i, j) \in E} min(a_j, a_i)}{d_i} +1 $，如果没有这个min，那这题就只能高斯消元解方程组才能得到答案。因为有这个 min，如果从小到大计算 $a_i$，方程就可以简化，步骤类似 Dijkstra 的松弛，从 $n$ 开始，通过方程已经计算的值，假设剩余未计算的都大于 $a_i$ 去估计 $a_i$，最小的一定是真的答案（发现选用大的一定不会让答案变得更小），set 维护即可。注意原图可能并不联通，可能影响迭代边界。
Problem H
Solved by ultmaster. 03:48 (+)
Problem J
Solved by zerol. 01:30 (+3)
Problem K
Unsolved.