母题
https://www.luogu.com.cn/problem/P5788
找每个数前面第一个大于它的。
基本思想:如果一个数出现的晚又大,那么它前面的数如果小者可以删去。
本题倒着做。
https://www.luogu.com.cn/record/164679827
-
https://www.acwing.com/activity/content/code/content/5712296/(这个变式比较重要,有相当一部分都从这延伸)
-
https://www.cnblogs.com/wscqwq/p/17579243.html对于每个位置求向上延伸有多少,然后枚举以这一行作为基底,就跟1.一样
-
https://www.cnblogs.com/wscqwq/p/17579257.html,3.的另一种解法,关注到了 \(a\) 的范围,枚举把小于的视为0,大于等于的视为1,然后做2.。
-
https://www.cnblogs.com/wscqwq/p/17579696.html,与2一样,由于是正方形所以长 $\times $ 宽时改一下。
-
https://www.cnblogs.com/wscqwq/p/17579821.html,与6一样,需要特判水平也会不合法(因为01交错)。
-
https://www.cnblogs.com/wscqwq/p/17488724.html,很特殊的单调栈,求字典序最小,所以可能与单调栈的优先级方面有关,研究发现如果后面的数小,而且前面的数有替代品(预处理一个数组)就可以弹栈(与普通单调栈很像)。
特性
发现2.~7.都是那种二维的问题,由于单调栈只能处理一维的问题,所以遇到两维,要么通过前缀和优化,要么使用枚举去掉一维,还可以二者一起使用(如4.)。
还有8.这种要求什么字典序最小的,只要是求最值,并且与位置有关(因为这道题是找排列的字典序最小,元素固定,位置决定成败)。
以后看到可能要单调栈的问题,考虑前缀和优化或枚举降维打击。
标签:www,cnblogs,html,wscqwq,https,com,单调 From: https://www.cnblogs.com/wscqwq/p/18290718