T1动态询问
这个题主要考察快速排序求第k小O(n)的时间复杂度完成的方法
主要错误原因在于,在一些情况下x与y并不连续,中间可能会各一个数,所以它的k需要注意
这道在这个点上卡了很久,大概花费了1h左右,但感觉应该可以更快的解决,主要在于那道题没学好,一直记了一个错误的算法
T2财富计算
这个题做的比较满意
就是逆序对的改编版,做了20min左右,没啥思维含量
T3频繁的数据
这道题在考试的时候就直接奔着暴力打了,拿到了60分
正解为:通过有序可得知这些出现x的部分一定是连续的,那么我们就可以计算出所有点的起始点,通过下标减长度再加一
然后早给定的区间中我们可以找到第一个开头大于等于l的,这些的答案都是长度,而剩下的一定是pos-l(pos是第一个开头大于等于l的点)
解决第一个问题可用RMQ解决
本题其实和第二讲第一题十分相似,所以还是要认真复习!
T4特技飞行
这道题在考试的时候也是直接打暴力,拿到了40分
正解:假设有两个点x,y,如果这两个点直接没有更大的或更小的,那么他们一定要相连,因为如果走中间的步数不会少,只会多,没有意义
所以这道题就可以就可以变成solve(l,x)+1+solve(y,r),就变成了一道分治的题
本题主要考点是分治还需要一些思维,然后还是要多练练这种题