XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea.¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 53/167 | 5 | 6 | 12 |
A¶
upsolved by 2sozx Bazoka13 JJLeo
题意¶
平面 \(n\) 个点，每个点有权值 \(v_i\)，现在可以选择一个点 \(p\)，点 \(p\) 的权值为所有 \(l \le dis(p, i) \le r\) 的点权和，最大化这个点权，其中 \(dis\) 表示的是切比雪夫距离。
\(n \le 10 ^ 5, l, r, \|x_i\|, \|y_i\| \le 10 ^ 9\)
题解¶
简单的转化一下，转变为 \(n\) 个点构成的方框所交的最大值，简单扫描线就可以做了。不知道什么问题，换了种扫描方式就过了，de了场上+场下好久找不出问题，迷惑。
B¶
upsolved by
题意¶
题解¶
C¶
solved by 2sozx
题意¶
有 \(n\) 座桥，每座桥有 \(k_i\) 个路段，不同桥间相互独立。每个路段有 \(p_{i, j}\) 的概率损坏，一座桥可以通行当且仅当这座桥的所有路段都完好。每次可以探寻一个路段是否损坏，问最少期望探寻多少次使得可以确定某一座桥可以通行或者所有桥均不能通行。
\(n, k_i \le 1000\)
题解¶
首先单独考虑每座桥，显然我们应该先问损坏概率大的桥，因此我们可以对每座桥的 \(k_i\) 个路段先排个序。
一个很显然的结论，如果我们询问了某座桥的某个路段，那么我们要一直问这座桥直到问到损坏或者这座桥的路段全部完好。
考虑访问桥的顺序，设 \(f_i\) 表示访问第 \(i\) 座桥的期望次数，\(pp_i\) 表示第 \(i\) 座桥能通行的概率，若 \(i\) 在 \(j\) 前面访问，则有 \(f_i + (1 - pp_i) \times f_j < f_j + (1 - pp_j) \times f_i\)，简单移项会发现 \(\frac{f_i}{pp_i} < \frac{f_j}{pp_j}\)，因此排序即可。
在知道了每座桥每个路段的访问顺序后，我们用 \(O(nk)\) 的转移即可。
E¶
solved by JJLeo Bazoka13
题意¶
一个半径为 \(R\) 的圆被分为 \(360,000\) 等份，初始有一些位置有点，两种操作：
- 在某个位置增加一个点
- 在某个位置删除一个点
初始中心还有一个半径为 \(r\) 的圆。
保证每时每刻每个位置不超过一个点，并且保证圆上最少有俩点，问每次操作后距离最远的两个点距离为多少。
\(q \le 10^5\)
题解¶
简单的想一下会发现中间的圆没用，对于每个点来说，距离最远的点就是离他对称位置最近的点，考虑线段树分治，这样就没有删除操作了。
考虑插入点，会发现只需要考虑这个点的最远距离即可，因此维护一个 \(set\)，即可。
计算距离时根据点对即可知道距离为多少。
F¶
solved by JJLeo
题意¶
给定 \(n\) 个点的完全图，找出最小距离生成树，即 \(\sum_{i, j}dis(i, j)\) 最小。
\(n \le 15\)
题解¶
考虑记录 \(f_{S, i}\) 表示 \(S\) 在 \(i\) 的子树中，\(i\) 为根的最小权值，可以暴力枚举另一个状态的根节点 \(j\) 转移即可。复杂度为 \(O(3^{n}n^2)\)，当然这里完全跑不满，因为 \(i,j\) 不会每次都是 \(n^2\) 的。
G¶
upsolved by
题意¶
给定一个图，定义以 \(i\) 为中心的最小生成树为原图中与 \(i\) 相连的边全被选的情况下最小生成树的权值，输出以每个点为中心的最小生成树权值。
\(n \le 10 ^ 5, n - 1 \le m \le 3 \times 10 ^ 5\)
题解¶
暂时还没过，暂时的想法
考虑随便搞一个最小生成树，对于每个点来说将其所连的边按深度排序，贪心的删除最小生成树上的最大边即可。
H¶
upsolved by
题意¶
题解¶
I¶
solved by JJLeo
题意¶
zyfgg带带
题解¶
zyfgg带带
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by
题意¶
题解¶
L¶
upsolved by
题意¶
题解¶
记录¶
0h：看了一圈感觉没有签到，MJX 看了 D 题意短给 ZYF 说了，不咋会。10min D过了很多人，想了想 D 可以做，ZYF开写，过了。把题都看了一遍没有很能写的，MJX 去玩玩 C，猜了个结论WA了。CSK 想 A，感觉可以转化一下，感觉完全对，ZYF 写扫描线了。
1h：ZYF 写完 A 交上去 WA 了，MJX 推了个 C 的式子，写完过了。ZYF 看 F 能直接跑状压开写，写完 WA 了。MJX CSK ZYF疯狂看 A。
2h：ZYF 看 F 发现一个地方写错了，改了过了。MJX 重写一遍 A，还是 WA 在同一个点。CSK 给 ZYF 讲了 E，ZYF 写其中一部分代码，CSK 等 ZYF 写完后写。
3h：CSK ZYF 写完过了，ZYF 看 I 就是可以在 SAM 上维护一堆东西，开写，写完过了。
4h：A 乱改还是不过。MJX ZYF 想了 G 的做法，最后 RE4，没调出来。
after end：A改了两次扫描线姿势就过了，为什么呢？