CF1810
div1+2
A.
存在一个 $i \geq x$ 就是 YES。
B.
首先如果 $n$ 是一个偶数,那么无解。
$\lfloor\frac{n-1}{2}\rfloor$ 和 $\lceil \frac{n+1}{2}\rceil$ 一奇一偶,递归构造即可。
1 | vector<int> ff; |
C.
首先答案有一个固定的上界,是全部删完之后加一个 $1$,因为不允许为空,即为 $n \times c + d$。
确定这个上界之后,枚举 $a_i$,假定最后的排列是 $[1, a_i]$,计算贡献即可。
D.
模拟题,记得开 ll。
E.
如果我选定了一个点,遍历到了一整个连通块,那么我一定找一个和联通块有边,且 $a_i$ 最小的一个点,来判断是否可行,这个很容易引导到一个启发式合并的思路,但是没有必要真的去启发式合并。
只需要维护一个堆,类似 dij 一样扩展就可以了。
F.
首先假设所有的叶子结点的深度为 $dep_i$,那么一定有 $\sum (\frac{1}{m})^{dep_i} = 1$。(显然)
然后考虑一个答案 $x$ 是否合法:
首先有 $a_i + dep_i \leq x$,那么可以得到 $\sum (\frac{1}{m})^{x-a_i} \leq \sum (\frac{1}{m})^{dep_i} = 1$
也就是 $\sum m^{a_i} \leq m^x$。
可以用线段树/珂朵莉树维护。
G.
如果使用 $dp_{i, j, k}$ 来表示前 $i$ 个的最大前缀和是 $j$,当前为 $k$,那么复杂度是 $n^3$ 。
每一维都删不掉,但是可以考虑反过来。
$f_i = \max(f_{i+1}+a_i, 0)$ ,用 $f_i$ 来表示 $[i, n]$ 的前缀最大值。
这启发我们可以设计状态 $dp_{i, j}$ 表示当前考虑到 $i$,$f_{i + 1} = j$ 的贡献。
1 | vector<long long> p(n), q(n); |
H.
咕咕。