link
赛时 240pts (50/50 + 100/100 + 90/150 + 0/200)
upd: 应该是 300pts，牛客的 SPJ 出锅了（

A

判断是否为相邻元素。
扫描一遍，判断位置绝对值之差是否为 1 即可

B

最简单的做法，断环成链，分别计算两个答案取 min 即可。
赛时写假了，我是绝对不会说我写了最短路而且没开 long long 的
警钟长鸣

C

构造题
令 b 数组的极差 $b^* = (a_i + a_j) - (a_k + a_l)$。由于要最小化极差，即最小化 $a_i + a_j$ 和最大化 $a_k + a_l$，且 $a_i + a_j \geq a_k + a_l$。由于是排列，因此不难想到将最大值与最小值放在一起，两两组合即可。

D

基础树形 dp 题
做法假了，遂看了题解 树形 dp只会没有上司的舞会 之后会刷会 dp 题
考虑设 $f_{i, 0}$ 和 $f_{i, 1}$ 分别表示第 i 个节点不染色，或者该节点及其儿子染色（不包括儿子的儿子）的最优方案数。
对于前者，有无染色没有影响，所以 $f_{i, 0} = \sum_{j \in son_i}{\max{(f_{j, 0}, f_{j, 1})}}$
对于后者，若 i 的儿子没有一个满足条件，就按照 $f_{i, 0}$ 的方法转移；若有满足条件的儿子，则在 $\max{(f_{j, 0}, f_{j, 1})}$ 与 $f_{i, 0} + f_{j, 0} + 2$ 中取较大者，其中后者表示先强制 i 和 j 都不染色，然后再染色的方案数，因此需要再加上 2。
注意到 $f_{i, 1}$ 的转移中需要用到 $f_{i, 0}$，因此 $f_{i, 1}$ 先转移，然后再计算 $f_{i, 0}$ （因为先计算 $f_{i, 0}$ 的话会让 $f_{i, 1}$ 的结果多加一遍 $\max{(f_{j, 0}, f_{j, 1})}$）。

总结：

树形 DP 常用 $f_{i, 0/1/...}$ 表示第 i 号节点选或者不选的状态。在考虑 $f_{i, k}$ 如何转移的时候，我们可以强制不选，利用已经计算好的 $f_{i, 0}$ 进行转移

Fighting~争取下次 AK
CSP rp++