C

均分纸牌的环形版,这里平均值为0

贪心

用了和均分纸牌一样的思路
就是若当前堆非0,则将这堆牌全都移到前一堆(无论正负)

均分纸牌直接从最后一堆开始,不过环形就得算出从每个位置开始移的答案
通过观察发现,从当前位置开始移动,使得每堆牌变成了一个数
若从下一堆开始,发现每堆的数目都减去前一堆的数目

所以我们扫一遍,统计每堆的个数
答案为 n - 个数最多的数目 即0最多的情况

D

给定一个序列,按序生成一棵二叉树,输出每个节点的父亲

二叉树

直接模拟可能退化成$O(n^2)$
我们发现若插入一个结点
其必为比之小一个位置的右孩子,或者大一个位置的左孩子
所以我们记录每个节点是否有左孩子和右孩子
在set中用upper_bound去判断插入结点的位置

E

给定序列$a_i$,当前位置i可以转移到$[i+1,a_i]$,代价为1
定义 $p_{i,j} \;\; i < j$ 为 i 转移到 j 的最小代价
求所有 $p_{i,j} \;\; i < j$ 的和

DP RMQ

定义 $d_i$ 为从i转移到 $[i+1,n]$ 的所有的最小代价和

$d_i = d_j + (n-i) - (a_i - j) \;\;$

其中 $a_j$ 为 $[i+1,a_i]$ 中的最大值