2019年牛客多校第二场 H题Second Large Rectangle

题目链接

传送门

题意

求在(n imes m)的(01)子矩阵中找出面积第二大的内部全是(1)的子矩阵的面积大小。

思路

处理出每个位置往左连续有多少个(1)，然后对每一列跑单调栈，记得处理由同一矩阵贡献的面积。

代码实现如下

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********
")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://Code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 1e5 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

stack<int> st;
int n, m, mx, mn;
int mp[1007][1007], vis[1007][1007];
int num[1007][1007], ls[1007], rs[1007];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            scanf("%1d", &mp[i][j]);
        }
    }
    for(int i = 1; i <= n; ++i) {
        int L = 0;
        for(int j = 1; j <= m; ++j) {
            if(mp[i][j] == 1) {
                ++L;
            } else {
                L = 0;
            }
            num[i][j] = L;
        }
    }
    for(int j = 1; j <= m; ++j) {
        while(st.size()) st.pop();
        for(int i = 1; i <= n; ++i) {
            while(st.size() && num[st.top()][j] > num[i][j]) {
                rs[st.top()] = i - 1;
                st.pop();
            }
            st.push(i);
        }
        while(st.size()) {
            rs[st.top()] = n;
            st.pop();
        }
        while(st.size()) st.pop();
        for(int i = n; i >= 1; --i) {
            while(st.size() && num[st.top()][j] > num[i][j]) {
                ls[st.top()] = i + 1;
                st.pop();
            }
            st.push(i);
        }
        while(st.size()) {
            ls[st.top()] = 1;
            st.pop();
        }
        for(int i = 1; i <= n; ++i) {
            if(vis[ls[i]][rs[i]]) continue;
            vis[ls[i]][rs[i]] = 1;
            int ans = num[i][j] * (rs[i] - ls[i] + 1);
            if(ans > mx) {
                mn = mx;
                mx = ans;
            } else {
                mn = max(mn, ans);
            }
            ans = num[i][j] * (rs[i] - ls[i]);
            if(ans > mx) {
                mn = mx;
                mx = ans;
            } else {
                mn = max(mn, ans);
            }
        }
        for(int i = 1; i <= n; ++i) vis[ls[i]][rs[i]] = 0;
    }
    printf("%d
", mn);
    return 0;
}