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.

Problem D

Solved by Weaver_zhu.

Problem E

Upsolved by Kilo_5723.

Problem F

Unsolved.

Problem L

SOlved by Kilo_5723.