P8783 [蓝桥杯 2022 省 B] 统计子矩阵_洛谷p8783思路

题目链接：[蓝桥杯 2022 省 B] 统计子矩阵 - 洛谷

解法一：暴力差分

代码：

#include<iostream>
using namespace std;
 
const int N = 505;
int a[N][N];
int n,m,k;
int cnt;
 
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>a[i][j];
            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)
        {
            big=false;
            for(int ii=i;ii<=n;++ii)
            {
                for(int jj=j;jj<=m;++jj)
                {
                    if(a[ii][jj]-a[ii][j-1]-a[i-1][jj]+a[i-1][j-1]<=k) cnt++;
                    else break;
                }
            }
        }
    }
 
    cout<<cnt<<endl;
 
    return 0;
}

解法二：差分+双指针

思路：

先确定上下边界x，y，再确定左右边界l，r，在确定lr时，可以用双指针法

若区间[l , r]符合条件，那么他的子区间也符合条件，符合的区间数为 r-l+1 个

若 [l , r] 不符合条件，那么[l , r + k ]一定不符合条件，进行l++再判断

这样只需O（n）时间复杂度就可确定处lr边界。

代码：

#include<iostream>
using namespace std;
 
typedef long long ll;
const int N = 505;
ll a[N][N];
ll tmp[N];
ll n,m,k;
ll cnt;
 
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&a[i][j]);
            a[i][j]+=a[i][j-1];
        }
    }
 
    for(int x=1;x<=m;x++)
    {
        for(int y=x;y<=m;++y)
        {
            for(int i=1;i<=n;++i) tmp[i]=a[i][y]-a[i][x-1];
            for(int i=1;i<=n;++i) tmp[i]+=tmp[i-1];
 
            int l=1,r=1;
            while(r<=n&&l<=n)
            {
                if(tmp[r]-tmp[l-1]<=k) cnt+=(r-l+1),r++;
                else l++;
            }
        }
    }
 
    cout<<cnt<<endl;
 
    return 0;
}