题目链接：https://pan.baidu.com/s/1nXgVYuGv-aavPk7vzkcjaw
提取码：hque
爬杆
50分做法
容易发现，如果可以加梯子，那么$i$到$j(i<j)$的距离是$h_i+h_j-2\min^j_{k=i}h_k+j-i$，因为必须要经过最小的位置。
其中$j-i$这⼀部分可以单独计算，$h_i+h_j$这部分也可以简单计算，剩下的部分是所有区间最小值的和，这个可以使⽤单调栈解决。
100分做法
⾸先建出笛卡尔树，也就是每次把序列⾥⾯最⼩的元素拿出来，然后递归左右两边建树。
然后我们考虑贪心的去加梯⼦，⾸先序列中所有的元素都要到达最小值。⽐如说序列是 x x x x x 1 x x x x x 2 x x x x ，那么⼀定是从$2$开始往左建高度为$2$的梯子，然后在和$1$相邻的时候把⾼度降为$1$，因为右边的所有值都不小于$2$，所以建高度低于$2$的梯⼦肯定是不优的。然后递归到左右两边继续处理。
具体做的时候，就对笛卡尔树进⾏dfs，同时记录⼀下左边这段区间已经摆放的梯⼦⾼度和右边区间摆放的梯⼦⾼度。如果左边区间梯子高度是$H_l$，并且当前节点的⾼度是$h_v$，左儿子的节点⾼度是 ，那么如果$H_l=Hu$，意味着我们可以直接从当前梯子高度⾛过来，否则我们要新建⼀段从$u$到$v$⾼度为$H_u$的梯⼦。
时间复杂度$O(n)$。
笛卡尔树
先找到一个最小值，然后再在左右两边分治。
变换
30分做法
枚举$k = 1,2,…,m$，将小于$k$的当成$-1$，等于$k$的当$1$，⼤于$k$的当成$1$，跑状压dp即可，可能要使⽤BFS。
60分做法
每两个 之间的都是独⽴的，所以我们思考⼀下每段需要多少步。
我们可以从两头开始依次把每个出变成$0$，比如⼀端是 0 1 1 这样，那么可以使⽤⼀次 操作将其变成 0 0 1 ，如果⼀端是 0 -1 1 的时候，那么我们只能先使⽤ 操作将其变成 0 1 1 ，然后接着操作。也就是如果有 -1 和 1 间隔，那么会额外进⾏⼀次操作，我们想让额外的操作次数尽量⼩。同时我们发现，如果有间隔的 1 -1 1 ，那么可以⽤⼀次$\max$操作将其变成 1 1 1 。
经过归纳总结⼀下，可以将序列划分成若⼲段极⻓的 1 与 -1 间隔的段，每段需要的额外的操作代价是⻓度除以$2$下取整。
100分做法
序列相当于被划分成了若⼲段，当且仅当两个数如果⾄少有⼀个是$0$或者两个数相同，那么会被划分开来。然后总代价是每段⻓度除以$2$下取整加上所有非$0$的数，所以当 从⼩到⼤变化的时候，我们⽤⼀个set维护⼀下每段的变化即可。
第三题
40分做法
状压dp即可。
100分做法
容易发现，Bob必胜的充要条件是存在完备匹配，由于这是⼀棵树，那么可以贪⼼地搞这个匹配。
令$dp(i,j)$表示$i$这个⼦树会有$j$个点没有被匹配，然后转移的时候就把⼦树所有没有被匹配的点加起来，选了$i$这个点，如果⼦树⾥⾯存在没有被匹配的点，那么没有被匹配的点会减$1$，否则会加$1$。
时间复杂度$O(n^2)$。
