2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14 [2020/10/22 08:55] jjleo [题解] |
2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14 [2020/10/22 09:35] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 81: | 行 81: | ||
| =====CF1420E===== | =====CF1420E===== | ||
| ====题意==== | ====题意==== | ||
| + | 给定一个 $\texttt{01}$ 串，每次操作可以交换相邻的两个 $\texttt{0}$ 和 $\texttt{1}$，问至多操作 $0$ 到 $\frac{n(n-1)}{2}$ 次，两者中间至少有一个 $\texttt{1}$ 的 $\texttt{0}$ 的对数最大值。 | ||
| ====题解==== | ====题解==== | ||
| + | 答案等于任意选 $\texttt{0}$ 的对数减去在连续 $\texttt{0}$ 段选的对数。 | ||
| + | 设 $pos_i$ 为第 $i$ 个 $\texttt{1}$ 的位置，一共有 $cnt$ 个 $\texttt{1}$，$f_{i,j,k}$ 表示第 $i$ 个 $\texttt{1}$，已经到第 $j$ 位，操作了 $k$ 次需要减去的对数的最小值，有如下转移方程：$$f_{i,j,k}=\min_{t=0}^{j-1}(f_{i - 1,t,k - |pos[i] - j|} + \frac{(j - t - 1) * (j - t - 2)}{2})$$ 对于每一个状态，最后还要减掉最后的一段 $\texttt{0}$，即为 $$ans_i=\frac{(n - cnt)(n - cnt - 1)}{2} - \min_{j=1}^{n}(f_{cnt,j,i}+\frac{(n - j)(n - j - 1)}{2})$$ 时间复杂度为 $O(n^4)$。 | ||
| =====CF1416D===== | =====CF1416D===== | ||
| ====题意==== | ====题意==== | ||
| + | 给出一张无向图，一开始第 $i$ 个点上面写着数字 $i$，有如下两种操作： | ||
| + | * 输出点 $x$ 所在连通块里面写着数字最大的点上面的数字，并将其改为 $0$。 | ||
| + | * 删除一条边。 | ||
| ====题解==== | ====题解==== | ||
| + | 考虑逆向过程，将删边改为加边，建出 Kruskal 重构树，非叶节点的权值代表子树中是第 $i$ 次删边操作前可以到达的连通块，之后倍增找祖先再套一个线段树维护 dfs 序，维护最小值和修改最小值即可。 | ||
| =====CF1408E===== | =====CF1408E===== | ||
| ====题意==== | ====题意==== | ||
| + | $m$ 个集合，里面放 $1$ 到 $n$ 的正整数。对于集合 $i$，如果里面有元素 $j$ 和 $k$，则在它们之间连一条颜色为 $i$ 的边。删除集合 $i$ 里面的数 $j$ 需要耗费 $a_i + b_j$ 的金钱，问使图不存在所有边颜色均不相同的环最少需要耗费多少钱。 | ||
| ====题解==== | ====题解==== | ||
| + | 新建 $m$ 个点代表每个集合，将集合里每个元素像对于集合代表的点连边，可以发现这样构造后原图有彩虹环等价于新图有环，直接求最大生成树即可，然后用总权值减去生成树上的边权之和。 | ||
| =====CF1408G===== | =====CF1408G===== | ||
| ====题意==== | ====题意==== | ||
2020-2021/teams/farmer_john/jjleo/2020.09.06-2020.10.14.1603328144.txt.gz · 最后更改: 2020/10/22 08:55 由 jjleo
