XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea
这场没罚时的。
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)
Problem L
Unsolved. (-3)