2020-2021:teams:farmer_john:2sozx:codeforces_round_639_unrated
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_639_unrated [2020/05/08 12:10] 2sozx [B] |
2020-2021:teams:farmer_john:2sozx:codeforces_round_639_unrated [2020/05/09 22:06] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| =====C===== | =====C===== | ||
| * 题意:给出$n(n\le2*10^5)$个变元和一个由$m(m\le2*10^5)$个不等式组成的式子，每个不等式为$x_i<x_j$，要求按$1$到$n$的顺序添加$n$个量词$\forall$与$\exists$使式子永真，要求$\forall$个数最多，或判断无解。 | * 题意:给出$n(n\le2*10^5)$个变元和一个由$m(m\le2*10^5)$个不等式组成的式子，每个不等式为$x_i<x_j$，要求按$1$到$n$的顺序添加$n$个量词$\forall$与$\exists$使式子永真，要求$\forall$个数最多，或判断无解。 | ||
| + | |||
| * 题解:如果出现环则无解。若有解则可贪心的从$1$至$n$选择$\forall$的使用,如果一个数已经是$\forall$,那么他所能达到的点一定是$\exists$,从$1$至$n$扫一遍即可 | * 题解:如果出现环则无解。若有解则可贪心的从$1$至$n$选择$\forall$的使用,如果一个数已经是$\forall$,那么他所能达到的点一定是$\exists$,从$1$至$n$扫一遍即可 | ||
| =====D===== | =====D===== | ||
| - | * 题意:长度为$n$的序列$a$,令$f={\sum_{i=1}^n}b_i(a_i-b_i^2)$,其中$0{\le}b_i{\le}a_i$且${\sum_{i=1}^n}b_i=k$,最大化$f$的值 | + | * 题意:长度为$n(n{\le}10^5)$的序列$a(a_i{\le}10^9)$,令$f={\sum_{i=1}^n}b_i(a_i-b_i^2)$,其中$0{\le}b_i{\le}a_i$且${\sum_{i=1}^n}b_i=k$,$k{\le}{\sum_{i=1}^n}a_i$,最大化$f$的值 |
| + | |||
| + | * 题解:对于序列中每一个位置$i$考虑如果$b_i+1$是什么情况,$f(b_i+1)-f(b_i)=a_i-3b_i^2-3b_i-1$,对于$b_i$是单调递减的,因此有一个显然的思路,即计算出每个位置的${\Delta}f(b_i)$,每次选择${\Delta}f(b_i)$最大的位置$i$进行操作,并将相应位置的$b_i+1$,由于$k$过大,因此我们可以二分最终的$\max{\Delta}f(b_i)$是多少即可 | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_639_unrated.1588911047.txt.gz · 最后更改: 2020/05/08 12:10 由 2sozx
