2020-2021:teams:farmer_john:2020.7.30
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020.7.30 [2020/07/31 17:06] 2sozx 创建 |
2020-2021:teams:farmer_john:2020.7.30 [2020/08/07 17:09] (当前版本) 2sozx [题解] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | [[https://codeforces.com/gym/289361|比赛链接]] | ||
| =====CF Expected diameter of a tree===== | =====CF Expected diameter of a tree===== | ||
| ====题意==== | ====题意==== | ||
| + | 给定一片森林，$q$ 此询问，每次给出两个点 $u,v$ ，如果 $u,v$ 在一棵树内输出 $-1$ ，否则在这两棵树任取一点临时建立一条边，求连边后的直径的期望。$n,q\le 10^5$ | ||
| ====题解==== | ====题解==== | ||
| + | 首先我们可以预处理出每个点在哪棵树中，其次预处理出每个点 $u$ 到这棵树叶子的最大值 $mx[u]$ ，这个可以用树形$DP$ 处理，将每棵树按照这个最大值进行排序，最后在处理出每棵树的直径长度 $len$ 。询问的时候枚举点数少的树，在另一棵树中寻找另一个点。将两棵树连接 $u,v$ 后的直径有两种情况： | ||
| + | * $mx[u]+mx[v]+1$ | ||
| + | * $\max(len[u],len[v])$ | ||
| + | 第二种情况是一个定值，因此对于每一个 $v$ 我们可以二分出满足第一种情况的 $u$ 的个数，剩余的即为第二种情况。最后答案要用 $map$ 记录下来避免重复询问。复杂度是神奇的 $O(n\sqrt{n}\log{n})$ | ||
| =====CF Selling Souvenirs===== | =====CF Selling Souvenirs===== | ||
| ====题意==== | ====题意==== | ||
| 行 28: | 行 34: | ||
| =====CF An overnight dance in discotheque===== | =====CF An overnight dance in discotheque===== | ||
| ====题意==== | ====题意==== | ||
| + | * $n$个只有相离和包含关系的圆，覆盖奇数次的区域为阴影，偶数次为空白，选择一些圆将原图分为两部分，每部分分别计算面积，使阴影部分面积最大 | ||
| ====题解==== | ====题解==== | ||
| + | * 第一种做法是贪心，即把覆盖两次的圆取出来，剩下的圆不动。 | ||
| + | |||
| + | * 关于证明，首先通过画图不难看出来，假设第二部分初始是空白的，那么将某个圆移动至第二部分，如果该圆覆盖区域变为阴影，那么总面积一定是增加或不变的，反之会减少或不变。 | ||
| + | |||
| + | * 同理，可以把圆转换为任意形状的闭合区域。 | ||
| + | |||
| + | * 当把覆盖两次的圆移动至左侧后，对于两次以上的圆，无论怎么移动，第二部分出现空白，总面积$\leq$最优面积 | ||
| + | |||
| + | * 如果移动覆盖一次的圆，实际上就是相当于把覆盖两次及以上的圆移动到第二部分，肯定是不优的。 | ||
2020-2021/teams/farmer_john/2020.7.30.1596186389.txt.gz · 最后更改: 2020/07/31 17:06 由 2sozx
