单调栈(最大子矩形强化版)——牛客多校第八场A

川长思鸟来 2023-10-11 09:14 9阅读 0赞

求01矩阵里有多少个不同的1矩阵

首先预处理出pre\[i\]\[j\]表示i上面连续的1个数，对每行的高度进行单调栈处理

栈里的元素维护两个值：pre\[i\]\[j\]和向前延伸最多能维护的位置pos

然后算贡献，从左往右扫时维护一个最靠右下面没有1的列的位置p，

元素在被弹出时判断其pos是否能包含p，如果能说明这个元素代表的矩阵是有贡献的

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int,int>pii;
    typedef vector<int>vi;
     
    #define rep(i,a,b) for(int i=(a);i<(b);i++)
    #define fi first
    #define se second
    #define de(x) cout<<#x<<"="<<x<<endl;
    #define dd(x) cout<<#x<<"="<<x<<" " ;
    #define pb(x) push_back(x)
    #define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
    const int N=5e3+5;
    char mp[N][N];
    int h[N][N];
    int area[N][N];
    int main()
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;++i)
            scanf("%s",mp[i]+1);
        
        memset(h,0,sizeof(h));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                if(mp[i][j]=='1'){
                    h[i][j]=h[i-1][j]+1;
                }
        int ans=0;
        for(int i=1;i<=n;++i){
            stack<pii>stk;
            int ma=-1;
            for(int j=1;j<=m+1;++j){
                int pos=j;
                while(!stk.empty()&&stk.top().fi>h[i][j]){
    cout<<stk.top().fi<<'\n';
                    if(stk.top().se<=ma){
                        ans++;
                    }
                    pos=stk.top().se;
                    stk.pop();
                }
                if(!h[i+1][j])ma=j;
                if(h[i][j]&& ( stk.empty() || (stk.top().fi<h[i][j]) ) )
                    stk.push(pii(h[i][j],pos));
            }
        }
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11332859.html