统计子矩阵题解

· · 题解

P8783 [蓝桥杯 2022 省 B] 统计子矩阵题解

由于 可亲可敬、美丽善良、孜孜不倦、德才兼备、德高望重、呕心沥血、披星戴月、尽心尽力、兢兢业业、鞠躬尽瘁、恪尽职守的（老师说太虚伪） wflengxuexnong让我们写一篇题解，于是，我写了这篇题解。

wflengxuenong

题目大意：

让你求在一个 N \times M 的二维矩阵中有几个子矩阵的和小于或等于给定的 K 。

思路：

前置芝士：二维前缀和

由于要快速求出矩阵的和来，所以我们要用到二维前缀和，如果您刚学，还不熟悉，先去刷一下这几道题：

一维的：T319882 2023山东入门组-T1-植树，P8218 【深进1.例1】求区间和

二维的：P3397 地毯

如果您已经很熟悉了，那请继续往下看。

那说到了前缀和，大家就很容易想到枚举矩阵的四个端点，然后求出这个矩阵的和，判断是否小于等于 k ，于是，一份暴力代码就此诞生。

暴力 code ：

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,k;
long long ans;
int a[N][N];
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//统计前缀和
        }
    }
    for(int i=1;i<=n;i++)//枚举行上的右端点
    {
        for(int j=1;j<=m;j++)//枚举列上的右端点
            {
            for(int d=0;h<i;h++)//枚举行上的左端点
                    {
                for(int l=0;l<j;l++)//枚举列上的左端点
                        {
                    if(a[i][j]+a[d][l]-a[i][l]-a[d][j]<=k)ans++;//求出这个矩阵的和，判断是否小于等于k
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

这可是得了整整80分！

接下来，我们来想一想如何优化它：

我们仔细看题，发现这道题的算法标签里有双指针！于是我们来考虑怎么利用双指针。

我们还是来枚举，这次我们枚举一行上的两个端点，然后我们让列上的右端点不断扩大，而左端点我们要找到第一个符合的左端点，于是我们写出了以下代码：

while(l<=r&&sum[r][j]-sum[r][i-1]-sum[l-1][j]+sum[l-1][i-1]>k)
{
    l++;
}

这样我们就找到了左右端点，于是我们就能AC了！

AC code：

#include<bits/stdc++.h>

using namespace std;

#define fst ios::sync_with_stdio(false);cin.tie();cout.tie();
#define Endl endl
#define itn int
#define For(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=b;i>=a;i--)
#define endl '\n'
#define re register
#define swap(a,b) a^=b,b^=a,a^=b
#define bit(x) (x&-x)
#define vi vector<int>
#define dg priority_queue<int>
#define xg priority_queue<int,vector<int>,greater<int> >

const int N=2e5+5;
const int P=1e9+7;

int n,m,k,a[501][501],sum[501][501];
long long ans;

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}

void write(long long x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

int main()
{
    n=read();//读入
    m=read();
    k=read();
    For(i,1,n)
    {
        For(j,1,m)
        {
            a[i][j]=read();//读入矩阵
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];//求前缀和
        }
    }
    For(i,1,m)//枚举列上的左端点
    {
        For(j,i,m)//枚举列上的右端点，注意j要从i开始，因为右端点一直是大于左端点的
        {
            int l=1;//行上的左端点
            For(r,1,n)//枚举行上的右端点
            {
                while(l<=r&&sum[r][j]-sum[r][i-1]-sum[l-1][j]+sum[l-1][i-1]>k)//左端点要直到i，j，l，r形成的矩阵中的和小于等于k
                {
                    l++;
                }
                ans+=r-l+1;//答案加上以i为列上的左端点，以j为列上的右端点，以r为行上右端点的矩阵的和小于等于k的矩阵的数量
            }

        }
    }
    write(ans);
    return 0; 
}