Educational Codeforces Round 83[CF1312]
这场比赛问题简单，但还是暴露的很多问题的。
G和E都花了太长时间了。证明自己的思维还是太慢。
Problem A
求正 $n$ 边形中选出 $m$ 个顶点是否能组成正 $m$ 边形。
显然：$m|n$。
Problem B
构造一种方案，将数组重排后，使得不存在 $i-a_i = j-a_j$ 的情况。
显然从大到小输出即可。
求方案数？
Problem C
一个数组，可以选择一个 $m$，然后对于每个 $i\in[1,m]$，将数组的某个位置减去 $k^i$。问是否存在一个 $m$，使得数组全为 $0$？
从大到小暴力即可。
Problem D
太长了，懒得写了。
先特判 $n=2$ 的情况。
枚举最大的那个的值以及位置，再枚举左右相等的那个点谁，然后组合数化简一下即可。
Problem E
题意
一个数列 $a$，每次可以将两个相邻且相等的数合成一个，权值加 $1$。
问数列 $a$ 最短能变成多少。
$n\leq 500$
题解
区间DP，看区间 $[i,j]$ 能否合成一个数 $k$，然后再一次 DP/bfs 就可以了。
时间复杂度 $O(n^3)$。
Problem F
留坑。。。
Problem G
为什么最后这道题这么简单啊。。。
题意
太长了，不写了。
题解
设在 $S$ 中的点为关键点。
显然考虑按dfs进行DP，设 $f_i$ 表示到 $i$ 这个节点的最短时间， $d_i$ 为深度，$s_i$ 为到考虑到当前的dfs序为止时，$i$ 的子树中的有多少个关键点。
若点 $i$ 不是关键点，有：$f_i=\min{f_j+d_i-d_j}$，其中 $j$ 为 $i$ 祖先。
若点 $i$ 是关键点，就会多一种转移： $f_i=\min{f_j+s_j}$，其中 $j$ 为 $i$ 祖先。
第二种转移需要支持区间 $+1$。即遇到一个关键点的时候需要令 $s_j$ 加上 $1$。
因此只需要实现一个单点覆盖和区间加，查询区间最大值的数据结构即可。
线段树/set/可删堆可以很轻松的维护。
时间复杂度 $O(n\log n)$。