CF1859

A

给定一个数组，要求把它分为两个非空数组 $S,T$，满足不存在 $a\in S,b\in T,~b|a$。
构造一组方案。
$n\le 10^5$

构造题，考虑观察性质。
发现若 \(b|a\) 有 \(b\leq a\)，那么只需把原数组中的所有最小值放到 \(S\) 中，其它全部扔到 \(T\) 中即可。

启发我们构造时应发掘性质，利用好那些 必要条件。

B

给定 n 个数列，每个长为 $m_i$。
现在可以把每个数列至多选一个数移动到另一个序列中。
最大化每个数列的最小值之和。
$n\le 2.5\times 10^4,2\le m_i,\sum m_i\le 5\times 10^4$

显然只会把最小值送出去，那么必然是要把这些最小值集中在一个地方。
（自己想的时候要分讨，但实际上是细节没刻画明白）
每个数列一定会把最小值送出去，然后再放到一个地方，这样是不劣的。
故我们可以用最小值和次小值来刻画贡献，\(\sum\limits g_{i}-\min(g_{i})+\min(f_{i})\)。

贪心的最优化有时 写成式子 可以去掉过程化的冗杂思考。

C

给定排列长度 n，构造这个排列，最大化 $\sum p_i\times i-\max(p_i\times i)$。
只需输出最优结果即可。
$n\le 500$

显然枚举最大值然后数据结构维护就可以做到 \(\mathcal O(n^{3}\log n)\)。
然而题解区有一种直接翻转后缀的做法。
贪心性可以理解，打表也能看出来，但是没法证。
傻逼猜结论没有证明（写题人在这证了一个半点，中途破防了好几次，也没有任何进展）。
代码

D

给定 n 个区间 $[L_i,R_i],[l_i,r_i]$，保证 $L_i\le l_i\le r_i\le R_i$。
每次可以从 $\forall x\in[L_i,R_i]\to \forall y[l_i,r_i]$。
给出 q 个询问，每次询问以 x 为出发能到达的最右位置。
$n,q\le 10^5$

贪心，注意到从 \((l_{i},R_{i}]\) 移动到 \([l_{i},r_{i}]\) 是注定不优的，对于 其余的情况每次都跳到 \(r_{i}\) 是最优的。
于是我们可以把每个区间都简化为 \([L_{i},r_{i}]\)，然后问题变为不断走区间的交能到达的最大右端点。
那么我们可以把所有相交区间合并起来，扫描线即可。

E

给定序列 $\{a_n\},\{b_n\}$，定义一个区间 $[l,r]$ 的权值为 $\lvert a_l-b_r\rvert+\lvert b_l-a_r\rvert$。
在序列上选择若干不交区间，使得其区间长度和为 $m$，最大化权值和。
$n,m\le 3\times 10^3$

不交区间 dp 有好性质。
考虑分析区间权值的性质，注意到 \(\lvert x \rvert\geq x\)，在求 \(\max\) 中有很好的性质。
故我们不需要分讨权值大小情况，只需直接爆枚举四种情况都取 \(\max\) 即可。
稍微拆一下式子，直接前缀最大值做即可。

F

给定一棵有边权树，有一些特殊点。
初始有 $c=1$，在特殊点上可以花费 $m$ 的时间强化使得 $c\leftarrow 2c$，此时经过一条边的时间是 $\lceil \frac{w_i}{c}\rceil$。
给出若干询问，每次问 $a\to b$ 的最短花费时间。
$n,q\le 10^5,w_i\le 10^9$

显然强化次数最多 \(\log V\)，可以枚举。
枚举后，答案一定形如，先走一段路径，走到特殊点再返回路径，然后走到终点。
注意到这个特殊点一定是 lca 的形式，那么只需维护对于任意一点算出先走到特殊点再走回来的最小路径，多源 dij 即可。
然后只需分讨那个点在哪，维护一个式子，由于静态直接倍增即可。

感觉实现比较麻烦，但是想起来比较简单。