1006国庆模拟题解
T1
emm……
首先思考一下题目的要求。
最简单最容易想到的，应该是(DFS)
然鹅……
今天代码实现的时候出了大问题……
进去出不来了……
淦！
于是只能骗分，也是能想到的最简单的骗分方式。
对于每一个(k==n-1)而言，
显然我们只能够选择保留一座山峰。
而无论保留哪座山峰，
我们都不会积水。
也就是说，积水体积为0。
这意味着我们只需要固输(n)即可。
50个点，过了2个。
简直是非常绝妙的 得分 骗分手段！！！
正解：
考虑(DP)
(f[i][j][p][0/1])表示前(i)列，最大值是(j)，且要求在后面存一个高度至少为(j)的土地。
已经铲平了(p)块。
当前积水体积为奇数/偶数的方案数。
由于至多会去掉(K)块土地，
所以对于任意一个(i),(j)的值只有(K+1)种。
前缀、后缀(DP)都做出，
枚举最终最大值所在列合并答案，
注意处理多个最大值的情况。
时间复杂度(P(NK^2))
T2
按照中序遍历和先序遍历贪心均可。
每一次检查当前点是否可以加入最终的树中，从当前点向上，每次遇到自己的左子树时，根据目前的情况计算右子树至少需要留下多少的点。
计算得到一个点留下整棵树至少多大，如果不超过(K)，则显然可以。
由于读入的树时(AVL)树，树高为(log N)。
时间复杂度(O(NlogN))
T3
我有思路的另外一道题。
直接暴力模拟，可以拿到(40)分。
显然，最终的挖掘方案一定可以按照深度从小到大的顺序操作。
那么在操作深度为(D)时，
小于(D)的所有深度相应区间的土地一定都消失了。
由于一次操作只可能影响同一个深度的土地，
所以我们可以将每一行看成一个独立的问题，
累加答案。
剩下的问题就是如何处理一行。
一个显然的贪心是区间中最靠前的一块土地肯定要被覆盖，
最优的方式就是将其作为长度为(K)的区间的第一个。
我们预处理出每个位置开始的倍增数组
时间复杂度(O(H(W+Q)logW))
T4
看不懂