P8783统计子矩阵

Hungry_STS · 2024-04-30 15:10:35 · 题解

题目传送门

三十分做法：

三十分做法就是一个暴力，我们可以枚举左上角和右下角，然后累加这个矩阵。

八十分做法：

这道题一眼看上去就是一个二维前缀和，我们可以用一个前缀数组存前缀和，之后我们枚举左上角和右下角用前缀和求出矩阵和，判断是否小于 K。时间复杂度 O(N^2M^2) 。

80分代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[505][505],s[505][505],k,sum=0;
int main()
{
    cin>>n>>m>>k;
    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]+a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int ii=1;ii<=i;ii++)
                for(int jj=1;jj<=j;jj++)
                    if(s[i][j]-s[ii-1][j]-s[i][jj-1]+s[ii-1][jj-1]<=k)
                        sum++;
    cout<<sum;
}

满分做法：

我们可以举一个一维的例子，因为 1 \le A_{ij} 所以如果前 i 项的和大于 K ，那么即使继续往后加和也是大于 K 的。所以我们可以类推过来，当四边形 (i \space j \space l \space r) 的和大于 K 的话，那么四边形 (i \space j+1 \space l \space r) 的和也大于 K 。

于是我们就能看出来，这是一个二维尺取。我们可以枚举 x 轴，去推 y 轴。i , j 正常枚举，在 y 轴上枚举 r ,当四边形 (i \space j \space l \space r) 的和大于 K 时让 l 加一。

AC代码：

#include<bits/stdc++.h>
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
long long n,m,a[505][505],s[505][505],k,sum=0;
int main()
{
    fst
    cin>>n>>m>>k;
    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]+a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int jj=1,ii=1;ii<=m;ii++)
            {
                while(s[j][ii]-s[i-1][ii]-s[j][jj-1]+s[i-1][jj-1]>k&&jj<=ii)
                {
                    jj++;
                }
                sum+=ii-jj+1;
            }
    cout<<sum;
}