单调栈 – Tgotp-Blog

4199: [Noi2015]品酒大会

竟然一遍ac了...万万没想到...

容易想到先求出SA,在hight数组上乱搞即可。。。

那么算某一个r就是区间min>=r的连续一段的组合之和。

考虑算多个r,因为大r肯定包含小r,那么算出了大r最后加到小r即可。

考虑这样怎么算,用单调栈维护一下即可,但是要注意在[......]

Read more

2096: [Poi2010]Pilots

维护两个单调栈随便搞搞就好了。

c++代码如下:

 

3238: [Ahoi2013]差异

辣鸡错误毁我时间。。。

ac与wa的区别。。。

用sa求出height即可,答案即为所有子区间最小值 之和,维护一个单调递增的单调栈。

c++代码如下:

 

1113: [Poi2008]海报PLA

我是个奇葩。。。这题都能想半天。。。

观察发现如果一个矩形能被省掉,那么前面比他高的所有情况中一定有一个和他相同的。。。

维护一个单调栈,最后比较一下top是否与当前值相同,相同的话此块可被前面覆盖,ans--。

c++代码如下:
[crayon-5ba570c2a7bb0231[......]

Read more