CF1935

E

Solution

• $c_j\ge 2$，此时令一个贡献 $2^j$，一个贡献 $2^j-1$，得到答案。
• $c_j=1$，贡献 $2^j$ 最优。
• $c_j=0$，无法产生贡献。

F

Solution

1. 若 $i=1$ 或 $n$，则所有连通块在可行时连 $mx \rightarrow mx+1$。
2. 若对于所有连通块 $x$，不存在 $mi_x<i<mx_x$，即所有连通块编号在 $i$ 两侧，我们将其分为左右集合，对于左集合右集合内部，用方案 $1$，再连边 $i-1 \rightarrow i+1$。
3. 若对于所有连通块 $x$，存在 $mi_x<i<mx_x$，则将所有 $mx_x < i$ 分为左集合，其余分为右集合，对于左集合，连 $mi \rightarrow mi-1$，右集合，连 $mx_x \rightarrow mx_x+1$。由于 $1$ 可能在左集合，这样会连一条边。我们找到右集合 $mi$ 最小值，连 $mi \rightarrow mi-1$。容易证明这样不会连成环。