XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea

From EOJ Wiki
Jump to: navigation, search

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.

题意:给定一个圆环上的点,有删点和加点操作,要维护环上最远距离。

题解:把每一个点的对点也加入到环上,就变成了维护环上两种颜色的点的最近距离。把所有的点都加到一个环上,显然我们只对相邻异色点的距离感兴趣。set 维护即可。

Problem F

Unsolved.

Problem L

Solved by Kilo_5723.

题意:给定一个循环序列 $\{a_n\}$,每一次把 $a_i$ 替换成 $a_i$ ~ $a_{i+m-1}$ 的异或和,求操作 $t$ 次之后序列的值。

题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。

根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k \mod 2\times len$ 的前缀异或和是相同的,因为循环节中长度等于 $2 \times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。