XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea
F0RE1GNERS
这场没罚时的。
Problem A
Solved by zerol. 02:43 (+)
题意：平面上有一些点，用一个回形的东西（就是到一个点的切比雪夫距离在一个区间内）去覆盖，问最多能覆盖多少点。
题解：每个点贡献一个回形的区域（看成加上一个正方形再减去一个正方形），然后求最大重叠点。扫描线即可。
zerol: 闭开区间保平安。
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)
盲人签到，听取 WA 声一片。
Problem E
Upsolved by ultmaster.
题意：在一个环上加点和删点，询问最远距离点对。
题解：用一个线段树维护『红点』和『蓝点』，红点就是原来的点，蓝点是红点旋转 180 度。这样问题就转换成求距离最近的红点和蓝点点对。维护区间最左边的蓝点、红点，最右边的蓝点、红点，以及答案。maintain 显然。
U: 不会写线段树，调了大半天。
Problem F
Solved by zerol. 04:53 (+8)
题意：求一棵生成树，最小化树上任意两点的距离和。
题解：就是求斯坦纳数的过程，状压 DP，由于树只会向一个方向涨，所以很容易计算出新增加的那条边对答案的贡献。
Problem L
Unsolved. (-3)
_
Problem A
Solved by Xiejiadong.
题意：给一个确定的回形区域，求覆盖的最大权值。
题解：离散化，扫描线。不过还要对于每一个点拆出他周围的两个点保平安。
Problem C
Solved by Kilo_5723.
题意：有 $n$ 条路径，每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏，现在每一次可以查询一条边是否损坏，问在采取最优策略的情况下，期望多少次查询能找到一条完整的路径，或者判断不存在一条完整的路径。
题解：对于每一个路径，优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后，我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$，那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times (t_{a_{n-1}} + p_{a_{n-1}} t_{a_n})\dots))$。我们发现，交换前后两项是可以直接算出来情况是否变得更优的。因此，用冒泡排序尝试找到最优的 {$a_n$}，并计算出答案。结果说明这么做是对的。
Problem D
Solved by Weaver_zhu.
Problem E
Upsolved by Kilo_5723.
Problem F
Unsolved.
Problem L
Solved by Kilo_5723.