2020牛客暑期多校训练营（第九场）J

Description

给定一个 (01) 矩阵，求其中有多少个连续子矩阵，满足边界（指最外面 (1) 层）都是 (1)，中间的 (01) 个数相差不超过 (1)。(n,m le 500)。

Solution

预处理出二维前缀和（(0) 当 (-1) 计）后，考虑暴力枚举上下边界，考虑夹出的这一部分。我们需要找到上下边界全是 (1) 的连续区间，考虑这些区间中全是 (1) 的列，对这些列用桶维护其前缀和，每次遇到一个合法列时，检查桶中前缀和相差为 (-1,0,1) 的个数，并将自己加入桶中。时间复杂度 (O(n^3))。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 505;

int a[N][N],s[N][N],n,m,t1,t2,t3,t4,c[N*N*2];

int sum(int i0,int j0,int i1,int j1)
{
    --i0;
    --j0;
    return s[i1][j1]-s[i1][j0]-s[i0][j1]+s[i0][j0];
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+2*a[i][j]-1;
        }
    }

    int ans=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                if(a[i][k]==0 || a[j][k]==0) continue;
                int l=k;
                while(a[i][l+1] && a[j][l+1] && l<m) ++l;
                if(k==l) continue;
                for(int x=k;x<=l;x++)
                {
                    if(sum(i,x,j,x)!=j-i+1) continue;
                    int id=sum(i+1,k+1,j-1,x-1)+n*m;
                    ans+=c[id-1]+c[id]+c[id+1];
                    c[id+sum(i+1,x,j-1,x)]++;
                }
                for(int x=k;x<=l;x++)
                {
                    if(sum(i,x,j,x)!=j-i+1) continue;
                    int id=sum(i+1,k+1,j-1,x)+n*m;
                    c[id]--;
                }
                k=l+1;
            }
        }
    }   
    cout<<ans<<endl;
    return 0; 
}