T1静音问题
这个题做的比较满意,主要考察单调队列,大概花费了10min左右
T2课后答疑
这个题卡了很久的暴力写法,大概一半多的时间都在调这道题的暴力写法,花了很久过掉暴力,然后就有点懵了,导致考试的时候没太想清楚怎么优化
但其实很简单,f[i]表示处理了前i个学生的问题的答案, 然后 f[i] 会从某个j转移过来,然后考虑用单调队列存这个j对应的f值,这样每次就可以取f值最小的位置了
T3最佳子序列
这道题在考试的时候打了一个暴力,拿到了40分
这道题其实是一个单调栈
就是维护什么时候x为最小值,通过单调栈就可以找出左边界与右边界了,然后计算答案即可
注意我们需要给a[n+1]设一个初始值,保证全部出栈
这道题其实应该一看就知道是一个单调栈,所以还要对单调栈这些更加熟悉
T4节日气氛
这道题在考试的时候没时间了,然后就没写
这道题主要是可以发现将这个摊位位置向右移一格,和之前唯一的差别在于以上一个位置为结尾的和以当前位置为开头的,那么我们就可以联想到滑动窗口,所以这道题也是一道单调队列
总结:这次考试都是有关于单调的,还是要好好复习单调队列,单调栈