ACM解题技巧---（单调栈）+ 题目总结-白红宇的个人博客

发布日期：2021-05-07 01:27:31 浏览次数：11 分类：技术文章

本文共 2363 字，大约阅读时间需要 7 分钟。

单调是一种思想，当我们解决问题的时候发现有许多冗杂无用的状态时，我们可以采用单调思想，用单调栈或类似于单调队列的方法去除冗杂状态，保存我们想要的状态

第一题

思路：栈里面去维护一个长方形的高，保持这个单调递增，遇到递减，就出栈然后更新。。。

AC代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include 
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 //#include 
                  
                   //#include 
                   
                    #include
                    
                     #include 
                     
                      #include 
                      
                       #define rsp(it,s) for(set
                       
                        ::iterator it=s.begin();it!=s.end();it++)#define inf_add 0x3f3f3f3f#define MOD 100000#define pb push_back#define mp make_pair#define fi first#define se second#define pi acos(-1.0)#define pii pair
                        
                         #define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1#define rep(i, x, y) for(register int i = x; i <= y; ++i)#define repd(i, x, y) for(register int i = x; i >= y; --i)#define file(s) freopen(s".in", "r", stdin), freopen(s".my", "w", stdout)using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
                         
                           P;typedef pair 
                          
                            pli;typedef pair 
                           
                             pil;typedef pair 
                            
                              pll;const double eps = 1e-6;template 
                             
                               void chkmax(T &x, T y) {x = max(x, y); }template 
                              
                                void chkmin(T &x, T y) {x = min(x, y); } template
                               
                                void read(T &x){ x=0;ll f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return;}// hdu 1506 // 求矩形的面积 + 单调栈 // 记得开ll 还有n == 0 特判断结束,不然WA const int maxn = 1e5+10;struct node{ ll w; // 宽度 ll h; //高度 }sa[maxn]; ll n, ans_area, cur_area, tot_w;stack
                                
                                 st;void input(){ while(scanf("%d",&n)!=EOF){ if(n==0) break; rep(i,1,n) read(sa[i].h),sa[i].w = 1; while(!st.empty()) st.pop(); ans_area = 0; st.push(sa[1]); rep(i,2,n){ //维护单调栈的性质 if(sa[i].h>=sa[i-1].h){ st.push(sa[i]); }else{ tot_w = 0,cur_area = 0; while(!st.empty()&&st.top().h>sa[i].h){ tot_w += st.top().w; // 总宽度乘以当前矩形高度 cur_area = tot_w * st.top().h; chkmax(ans_area,cur_area); st.pop(); } sa[i].w +=tot_w; st.push(sa[i]); } } //最后就是把单调栈的值更新就行 tot_w = 0; cur_area = 0; while(!st.empty()){ tot_w += st.top().w; cur_area = tot_w * st.top().h; chkmax(ans_area,cur_area); st.pop(); } printf("%lld\n",ans_area); }}void solve(){ }int main(){ //ios::sync_with_stdio(false); //cin.tie(0); #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #if __cplusplus >= 201103L auto start = steady_clock::now(); #endif #endif input(); // solve(); return 0;}

第二题：

持续更新中…

上一篇：CSS中a标签（元素）字体颜色继承问题（详细解释）（以及解决方法）

下一篇：Linux学习笔记---（Mysql安装与初始化）（傻瓜式安装）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

单调是一种思想，当我们解决问题的时候发现有许多冗杂无用的状态时，我们可以采用单调思想，用单调栈或类似于单调队列的方法去除冗杂状态，保存我们想要的状态

第一题

AC代码

第二题：

持续更新中…

发表评论

最新留言

关于作者

推荐文章