Difference between revisions of "XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea"
Xiejiadong (talk | contribs) |
|||
| (4 intermediate revisions by one other user not shown) | |||
| Line 70: | Line 70: | ||
题意：有 $n$ 条路径，每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏，现在每一次可以查询一条边是否损坏，问在采取最优策略的情况下，期望多少次查询能找到一条完整的路径，或者判断不存在一条完整的路径。 | 题意：有 $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$} | + | 题解：对于每一个路径，优先查找最可能坏掉的边。计算出第 $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 == | == Problem D == | ||
| Line 91: | Line 91: | ||
Solved by Kilo_5723. | 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))$ 的。 | ||
Latest revision as of 07:15, 9 September 2019
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))$ 的。