题解：CF375B Maximum Submatrix 2

· · 题解

Problem - 375B - Codeforces

计数排序

题意简述

只移动行，求由 1 构成的最大矩阵的面积。

思路

枚举每一列，对该列每行往左的 1 的数量排个序，找最大面积。

下面用 - 表示 1，进行演示操作（假设有 3 行，枚举到第 j 列，对于大于 j 的列，可以暂时不管）。

     j
   --- (3)
 ----- (5)
    -- (2)

排序得（升序，降序都行，这里用降序）：

     j
 ----- (5) h=1,S=5*h=5
   --- (3) h=2,S=3*h=6
    -- (2) h=3,S=2*h=6

所以对每一列求出来的 1 的数量，直接用 sort 排序似乎就可以了？

但是！！！

算一下此时的时间复杂度 O(n^2\log n)，当 n=5000 时，5000\times 5000\times 13\approx 3\times 10^8，这时需要 3 秒才能过。

而题目要求是 2 秒，有超时风险。

所以考虑优化：

用计数排序，记录该列每个宽度出现的次数，然后从大到小枚举，就可以优化为 O(n^2)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair<int, int>
const LL mod = 998244353;
const int N = 5010;
int a[N][N];
int len[N][N];//表示第i行，以第j列为右边界，向左连续1的个数
int cnt[N]; //每个宽度出现的次数
int ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin>>n>>m;
    string s;
    for (int i = 1; i <= n;i++){
        cin >> s;
        s = " " + s;
        for (int j = 1; j <= m;j++){
            a[i][j] = s[j] - '0';
        }
    }
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++){
            if(a[i][j]==1){
                len[i][j] = len[i][j - 1] + 1;
            }else{
                len[i][j] = 0;
            }
        }
    }
    for (int j = 1; j <= m;j++){//对每一列操作
        for (int i = 0; i <= m;i++){//注意，记得清空
            cnt[i] = 0;
        }
        for (int i = 1; i <= n;i++){
            cnt[len[i][j]]++;
        }
        int h = 0;
        for (int i = m; i >= 1;i--){
            h += cnt[i];
            ans = max(ans, h * i);
        }
    }
    cout << ans << endl;
}

提交记录