• 欢迎光临~

队列与栈

开发技术 开发技术 2022-08-06 次浏览

栈的最基本用途可能就是表达式求值了

P1310 [NOIP2011 普及组] 表达式的值

大概捋一下转化过程
如果是左括号或乘号,直接入栈
如果是右括号,一直弹栈知道出来左括号
如果是加号,则先弹栈直到没有乘号
乘号就直接放

单调栈

单调栈是一种快速求解序列中每个位置左右第一个大于/小于自己值的位置的算法,在大部分情况下可以很好地代替笛卡尔树

具体流程省略


P4147 玉蟾宫

把一维变成二维了而已,预处理每行上方最长连续高度即可,然后再跑最大矩形

这里再介绍一下悬线法

首先预处理 (up[i][j]) 表示向上最大高度,即悬着的“线”
那么对于每条线只要知道左右最远能移动到的位置即可
(l[i][j])(r[i][j]) 就是这个左右
如果上一行这一列不是障碍,那么 (l,r) 分别取 (min),否则意味着开启一块新的矩形


CF1601E Phys Ed Online

首先肯定是每个模 (k) 同余系都单独拎出来做
答案为 (a_l+min(a_l,a_{l+1})+min(a_l,a_{l+1},a_{l+2})+dots)
设后面第一个比 (i) 小的位置为 (nxt_i),则答案为 (sum (nxt_i-i)a_i)
那么就对单调栈上的这个东西做前缀和
具体询问的时候可以发现区间内只要最后一级的值会发生变化,即最小值的位置,这个可以手动算出,其它直接前缀和相减

  • 单调性相关题目中单调栈上做前缀和比较常见

单调队列

单调队列可以用于优化如下类型的 (dp) 转移:

[f_i=max_{l_ile jle r_i}{f_j+val(i,j)} ]

要求 (l_i)(r_i) 单调,且 (val(i,j)) 之和 (i)(j) 中的一个有关(指没有乘积项)


下面的例子直接写出 (dp) 方程来进行优化

  • fence

[f[i][j]=max_{j-l_ile kle S_i-1}{f[i-1][k]+P_i(j-k)} ]

发现 (val) 部分只与 (k) 有关,而当 (j) 变大 (1) 的时候,候选 (k) 集合也是单调的,那么用单调队列维护即可


  • cut the sequence

[f[i]=min_{0le j<i&&sum_{k=j+1}^i}{f[j]+max_{j+1le kle i}{a_k}} ]

经过证明,可以发现最优候选 (j) 满足两个条件之一:

  1. (j) 是满足和条件的最小的
  2. (j)([j+1,i]) 的值都大

那么可以维护一个单调递减的队列,存放所有合法的 (j)
但是注意这时 (a_j) 最大不能代表最优转移,而是将 (f[j]+max{a_k}) 都放入堆中,动态查询出一个最大的转移


tricks

队列在动态最值中的应用

P2827 [NOIP2016 提高组] 蚯蚓

以这道题为例


P7078 [CSP-S2020] 贪吃蛇

毕竟蛇与蚯蚓是类似的生物,这道题中也用到了类似的思想,详见这篇博客


P6033 [NOIP2004 提高组] 合并果子 加强版

构建哈夫曼树的时候同样可以用这种方式代替过慢的堆


B. 第二题

甚至跑最长路都可以用这种技巧优化


总之用到堆并且时间挺卡的题都想想这个吧~

队列与栈的转化

棋盘

矩乘啥的都先不说了
可以发现维护出的前缀积当队首出队时贡献是不能刨去的,因为不满足交换律
那么维护两个栈,每次有插入操作直接插在第二个栈后面,有删除操作,能弹第一个就弹第一个,否则把第二个栈中所有元素拿出来放进第一个,顺便处理前缀积
这样很好地做到了矩乘顺序的倒序,而每个元素出栈一次,复杂度也得到了保证


P1295 [TJOI2011]书架

(dp) 方程是 (f_i=min (f_j+max[j+1,i])(sum_{j+1}^i ale m))
首先合法左端点是单调的,(f) 是单调的,(max) 是单调的
那么合法转移点一定是 (a) 单调的,且队列中 (f_{q_j}+a_{q_{j+1}}) 来更新答案
那么问题是需要快速求出单调队列的最小值
可以用栈来代替队列,每次取 (mid) 向左右构建单调栈

简要分析一下复杂度,从单调队列删除的总次数为 (n) 次,而每一次重构以后再删除 (frac{len}{2}) 的长度才会重新重构,所以复杂度为 (O(n))


双端队列可以用于 (01) (bfs),对于 (0) 边转移放在前面,(1) 边转移放在后面即可

程序员灯塔
转载请注明原文链接:队列与栈
喜欢 (0)