CF1856

A

将条件转化为 \(\binom{n}{2}\) 个有序数对 \((i,j)\)，二元关系，若 \(a_i>a_j\)，则至少需要 \(a_i\) 的时间，对每个满足要求的 \(a_i\) 取 \(\min\) 即可。

B

关注正整数的条件，考虑转化，将 \(a\) 同时减一，转化成非负整数。考虑构造，关注特殊，如果 \(a_i\ne 0\)，那么 \(b_i=0\)，否则 \(b_i=1\) 。这样 \(b\) 的和最小，如果 \(b\) 的和大于 \(a\) 的和，那么必然无解。否则如果 \(n>1\)，则容易构造必然有解。

总结：思考过程中，都要思考特殊，恰好等于 可以转化为先 小于等于，再加到等于。

类似与二项式反演，等于转化小于等于，或者 DP 状态设计 小于等于 等。

C

换元转化，关注最后的最大值的位置 \(p\) 。如果它达到 \(x\)，关注最右端操作的 \(r\)，那么 \(r\) 至少需操作到 \(x-(r-p)\)，且 \([p,r]\) 构成递减的公差为 \(1\) 的等差数列，这是充要的。考虑将枚举 \(x\) 转化成二分 \(x\)，复杂度 \(\mathcal{O}(n^2\log V)\)

D

关注最大值位置 \(p\)，关注位置 \(p\) 成为最大值的条件 / 性质。考虑对于 \(l<p\)，有 \(c(l,p)-c(l,p-1)=p-l\)，或者对于 \(r>p\)，有 \(c(p,r)-c(p+1,r)=0\) 。从特殊推广到一般，那么对于 \(l,r\)，我们可以通过 \(2\) 次操作判断 \(l\) 或 \(r\) 是否为区间最大值。

trick：交互题，查找量，可以考虑维护可行集合 \(S\)，每次从 \(S\) 中删除。

我们考虑维护可行集合 \(S\)，贪心，每次选择 \(|i-j|\) 最小 \((i,j)\)，删除一个，由鸽巢原理可知，对于 \(|S|=i\) 时，至少存在一个区间 \(\text{len}\le \frac{n}{i}\)，那么总操作次数不超过 \(n+2\sum(\frac{n}{i})^2\)

我们知道 \(\sum\limits_{i=1}^{n}\frac{1}{i^2}\le 2-\frac{1}{n}\)，那么原式 \(\le 4n^2\) 。

或者考虑 序列分治，从下到上，考虑求出左右区间的 \(\max\)，再比较，次数为 \(2\sum\limits (\frac{n}{2^i})^2 2^i=2\sum n2^i\le 4n^2\)

或者考虑 特殊情况，关注 \(\forall\;l\)，操作 \([l,l+1]\)，序列至少减半，从特殊推广到一般，每次减半，容易发现就是 分治，从下到上，只不过去了向下分治的过程。注意这里只能间隔操作，序列元素少了，间隔就大了，可能不优，操作次数不正确。

E1 & E2

树上问题，考虑 顺序，从下到上（按子树考虑），考虑 DP。发现我们只关注 相对大小 ，那么就不需要记录值域。其次考虑对于 \(u\) ，我们只关心它的儿子的 \(siz\) 的大小，不关心具体形态。最优化，考虑什么情况最优。贡献只能由两个不同的子树产生，那么猜测必然由一部分子树的权值小于 \(a_u\)，其余大于 \(a_u\) 。证明考虑设除子树 \(v\)，大于 \(a_u\) 的点个数为 \(b\)，其余点个数为 \(c\)，使得贡献最大，必然让子树内的点全部贡献在 \(\max\{b,c\}\) 上，则必然子树内要么小于 \(a_u\)，要么大于 \(a_u\) ，暴力 01 背包即可，复杂度 \(\mathcal{O}(n^2)\)