2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated [2020/05/07 22:29] jjleo [C] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated [2020/05/10 22:07] (当前版本) jjleo [C] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| =====C===== | =====C===== | ||
| - | * 题意:离 散 数 学，给出$n$个变元和一个由$m$个不等式组成的合取式，每个不等式形如$x_i<x_j$，要求按$1$到$n$的顺序添加$n$个量词（全称量词或存在量词）使得其成为永真式，要求全称量词的数量最少，或判断无解。 | + | * 题意:离 散 数 学，给出$n$个变元和一个由$m$个不等式组成的合取式，每个不等式形如$x_i<x_j$，要求按$1$到$n$的顺序添加$n$个量词（全称量词或存在量词）使得其成为永真式，要求全称量词的数量最**多**，或判断无解。 |
| - | * 题解:按照不等式建出有向图，如果有环显然无解，因为自己不能小于自己。按照$1$到$n$的顺序遍历每个点，如果这个点能到达的某个点或能到达这个点的某个点已经被访问过了，那么显然这个点不能任意了，否则可以任意。因此先判环，然后建正图和反图， | + | * 题解:按照不等式建出有向图，如果有环显然无解，因为自己不能小于自己。按照$1$到$n$的顺序遍历每个点，如果这个点能到达的某个点或能到达这个点的某个点已经被访问过了，那么显然这个点不能任意了，否则可以任意。因此先判环，然后建正图和反图，分别dfs即可。注意vis数组对于正图和反图要分别建，比赛的时候合一起就WA了，因为在正图被访问的时候并不能继续访问反图里面能访问的点。 |
| + | |||
| + | =====D===== | ||
| + | * 题意:给出一个序列$a_i$，求序列$b_i$使得$\sum\limits_{i=1}^n b_i(a_i-b_i^2)$的最小值，其中要求$0\le b_i \le a_i$且$\sum\limits_{i=1}^n b_i=k$。 | ||
| + | |||
| + | * 题解:对于某一个$i$，当$b_i$为$x$时，如果令其加$1$，对答案的贡献为$\Delta_i (x):=\left[x(a_i-x^2)\right]-\left[(x-1)(a_i-(x-1)^2)\right]=a_i-3x^2+3x-1,$，可以看到这个二次函数是开口向下而且顶点横坐标在$\frac{1}{2}$，因此在本题定义域中是严格单调递减的。我们可以让所有$b_i$为$0$，然后贪心地看给哪个$b_i$增加$1$的贡献最大就增加哪个。由于$k$太大，因此我们二分每次增加$1$所产生贡献的最小值，对于要验证的值，再套一个二分（或者解方程）算每个$bi$可以加几次，保证总和大于等于$k$，最后如果总和超出$k$，一定可以将多余的增加值等于二分出来的值的$b_i$减少$1$，否则二分的值可以更小。 | ||
2020-2021/teams/farmer_john/jjleo/codeforces_round_639_unrated.1588861761.txt.gz · 最后更改: 2020/05/07 22:29 由 jjleo
