2020-2021:teams:farmer_john:2020.8.2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020.8.2 [2020/08/07 14:59] 2sozx 创建 |
2020-2021:teams:farmer_john:2020.8.2 [2020/08/07 21:10] (当前版本) 2sozx [题解] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| [[https://codeforces.com/gym/289702|比赛链接]] | [[https://codeforces.com/gym/289702|比赛链接]] | ||
| - | =====CF Expected diameter of a tree===== | + | =====CF Karen and Test===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Selling Souvenirs===== | + | =====CF Karen and Supermarket===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Card Game===== | + | =====CF Choosing The Commander===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Anthem of Berland===== | + | =====CF MEX Queries===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Glad to see you!===== | + | =====CF Sofa Thief===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Vladik and Favorite Game===== | + | =====CF Level Generation===== |
| ====题意==== | ====题意==== | ||
| + | $q$ 次询问，每次给出一个 $n$，问 $n$ 个点最多能连几条边使得桥的个数大于等于边数的一半。 $q\le10^5,n\le2\cdot10^9$ | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Sagheer and Apple Tree===== | + | 考虑 $n$ 个点最多形成 $n-1$ 个桥，因此将 $n$ 个点顺次链接。现在考虑向其中加边，若前 $x$ 个点构成了完全图，显然之后是依次连接 $1\sim x$ 和 $x+1$ 最优，因此我们考虑 $x$ 最大为多少。 $x$ 要满足以下式子：$$sum=C(x,2)+n-x,n-x\ge \frac{ans}{2}$$合并得到 $x^2+x\le2n$，可以通过解方程 $O(1)$ 得到。接下来考虑加边，考虑桥的数量和非桥边的数量的差值 $s$，要求 $s\ge0$ ，加的第一条边会增加两条非桥边并且减少一条桥边， 即 $s=s-3$ ，之后每加一条边 $s=s-1$，因此当 $s\ge3$ 时可以增加 $s-2$ 条边 ，否则不可以加边，因此每个询问可以 $O(1)$ 计算出答案。 |
| + | =====CF Mister B and Boring Game===== | ||
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Army Creation===== | + | =====CF Jon and Orbs===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF Bipartite Checking===== | + | =====CF Broken robot1===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| - | =====CF An overnight dance in discotheque===== | + | =====CF Okabe and City===== |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
2020-2021/teams/farmer_john/2020.8.2.1596783589.txt.gz · 最后更改: 2020/08/07 14:59 由 2sozx
