2020-2021:teams:farmer_john:2020.8.2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020.8.2 [2020/08/07 15:02] 2sozx |
2020-2021:teams:farmer_john:2020.8.2 [2020/08/07 21:10] (当前版本) 2sozx [题解] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| =====CF Level Generation===== | =====CF Level Generation===== | ||
| ====题意==== | ====题意==== | ||
| + | $q$ 次询问，每次给出一个 $n$，问 $n$ 个点最多能连几条边使得桥的个数大于等于边数的一半。 $q\le10^5,n\le2\cdot10^9$ | ||
| ====题解==== | ====题解==== | ||
| + | 考虑 $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 Mister B and Boring Game===== | ||
| ====题意==== | ====题意==== | ||
2020-2021/teams/farmer_john/2020.8.2.1596783762.txt.gz · 最后更改: 2020/08/07 15:02 由 2sozx
