C - Linear Approximation
取 \(a_i-i\) 的中位数即可。
D - Equal Cut
考虑枚举第二个分割点，那么考虑另外两个分割点每一个都只有两种可能：最后一个使得前一段和小于等于后一段和的位置或者这个位置再往后一个。这两个分割点的位置随第二个分割点向后移动也是单调向后移动的，双指针维护即可。
E - Or Plus Max
直接 dp 记录 \(i\) 的子集中的最大值和次大值，转移考虑用删除任何一个元素后 dp 数组更新自己或者是添加 \(a_i\)。最后输出答案只需做一遍前缀 max。复杂度 \(O(n2^n)\)。
F - Colorful Sequences
问长度为 \(n\)，每个元素是 \([1,k]\) 中的整数的好的序列中长为 \(m\) 的序列 \(A\) 出现的总次数，其中好的序列定义为存在一个长为 \(m\) 的连续子序列使得 \([1,k]\) 中每个整数在其中各出现一次。\(n\leqslant 25000,k\leqslant 400\)。
我们考虑用所有序列中 \(A\) 的出现次数减去不好的序列中 \(A\) 的出现次数。显然所有序列中 \(A\) 的出现次数总和为 \((n-m+1)k^{n-m}\)，现在我们只需考虑后者。
如果 \(A\) 是好的，那么不好的序列中 \(A\) 的出现次数为 \(0\)，现在考虑 \(A\) 不是好的的情况。
我们先做一个 dp，设 \(f(i,j)\) 表示有多少长为 \(i\) 的不好的序列，极长元素互不相同后缀长度为 \(j\)。转移只需要枚举最后一个数是否与第 \(i-j\) 个数相同，于是有转移方程 \[ f(i,j)=(k-j+1)f(i-1,j-1)+\sum\limits_{t=j}^{k-1}f(i-1,t) \] 这个只需要前缀和优化一下可以做到 \(O(nk)\)。
现在回到刚才的问题，先考虑如果 \(A\) 中元素两两不同（此时 \(m<k\)）的情况。我们可以发现，所有不好的序列中 \(A\) 的总出现次数等于长度为 \(m\) 的两两不同的子串的总出现次数除以 \(\dfrac{k!}{(k-m)!}\)。那么我们再设一个 dp 数组 \(g(i,j)\) 表示所有 \(f(i,j)\) 种不合法序列中长度为 \(m\) 的两两不同的子串的总出现次数，\(g\) 的转移和 \(f\) 几乎完全一致，只需要对每个 $jm $ 额外加上 \(f(i,j)\) 即可。
现在考虑 \(A\) 中元素有相同的情况，我们设极长元素互不相同前缀/后缀分别为 \([1,l],[r,n]\)，我们注意到不可能有一个长为 \(k\) 的排列跨过了 \((l,r)\)，故我们只需要固定 \(A\) 的开头位置，只需要分别保证 \(l\) 前面和 \(r\) 后面合法即可，计算方案数可以套用刚才的 dp，只需要把刚才的 dp 略微改动，分别让初值为 \(f(0,l)=1\) 与 \(f(0,m-r+1)=1\) 即可。