Warning: session_start(): open(/tmp/sess_6ac0f4ee59f3f2f9c3e9a955717ec94f, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
[[https://codeforces.com/gym/289361|比赛链接]]
=====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 Card Game=====
====题意====
====题解====
=====CF Anthem of Berland=====
====题意====
====题解====
=====CF Glad to see you!=====
====题意====
====题解====
=====CF Vladik and Favorite Game=====
====题意====
====题解====
=====CF Sagheer and Apple Tree=====
====题意====
====题解====
=====CF Army Creation=====
====题意====
====题解====
=====CF Bipartite Checking=====
====题意====
====题解====
=====CF An overnight dance in discotheque=====
====题意====
* $n$个只有相离和包含关系的圆,覆盖奇数次的区域为阴影,偶数次为空白,选择一些圆将原图分为两部分,每部分分别计算面积,使阴影部分面积最大
====题解====
* 第一种做法是贪心,即把覆盖两次的圆取出来,剩下的圆不动。
* 关于证明,首先通过画图不难看出来,假设第二部分初始是空白的,那么将某个圆移动至第二部分,如果该圆覆盖区域变为阴影,那么总面积一定是增加或不变的,反之会减少或不变。
* 同理,可以把圆转换为任意形状的闭合区域。
* 当把覆盖两次的圆移动至左侧后,对于两次以上的圆,无论怎么移动,第二部分出现空白,总面积$\leq$最优面积
* 如果移动覆盖一次的圆,实际上就是相当于把覆盖两次及以上的圆移动到第二部分,肯定是不优的。