P8783

hatred · 2024-04-30 15:12:55 · 题解

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

题目大意： 给定一个 N×M 的矩阵，统计有多少个矩阵内所有数的和不超过K。

题目思路：

80分做法（暴力）：

1.定义N,M,K,a[500][500],sum[500][500]，ans;

2.输入N,M,K；

3.用两个for循环把矩阵中的数全输入到a数组里，把sum数组里放入a数组的前缀和:

sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];

4.在前缀和操作之后用两个for循环枚举可能存在的长方形，再求和与K比较；如果小则计数器ans++;

5.输出ans；

#include<bits/stdc++.h>
using namespace std;
const int N=501;
long long n,m,k,ans=0,a[N][N],sum[N][N];//定义 
int main() {
    cin>>n>>m>>k;//输入 n,m,k
    for(long long i=1; i<=n; i++) {// 枚举行 
        for(long long j=1; j<=m; j++) {// 枚举列 
            cin>>a[i][j];// 输入矩阵 
            sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//求前缀和 
            for(long long h=0; h<i; h++) {//枚举比现在小的行数 
                for(long long l=0; l<j; l++) {// 枚举比现在小的列数
                    if(sum[i][j]+sum[h][l]-sum[i][l]-sum[h][j]<=k) {// 枚举可能存在的长方形,求和与K比较
                        ans++;//计数器加一 
                    }
                }
            }
        }
    }
    cout<<ans;//输出计数器 
    return 0;
}

100分做法：

前三步和80分做法一样，但之后就不一样了；

4.退出for循环，再建三个for循环，设int i=1;i<n;i++//int j=i;j<n;j++//int l=1,r=1; r<=m; r++(其中i和j枚举行，l和r是指针 枚举列）

5.在for循环里建一个while循环，条件是l<=r&&sum[j][r]-sum[i-1][r]-sum[j][l-1]+sum[i-1][l-1]>k; 在while循环里l++; 这是枚举所有长方体，但与80分做法不同的是能一次在一行找到所有符合条件的长方体；

6.ans+=r-l+1；

7.输出ans；

#include<bits/stdc++.h>
using namespace std;
const int N=501;
long long n,m,k,ans=0;
long long a[N][N],sum[N][N];
int main() {
    cin>>n>>m>>k;
    for(long long i=1; i<=n; i++) {
        for(long long j=1; j<=m; j++) {
            cin>>a[i][j];
            sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    for(long long i=1; i<=n; i++) {
        for(long long j=i; j<=n; j++) {
            for(long long l=1,r=1; r<=m; r++) {
                while(l<=r&&sum[j][r]-sum[i-1][r]-sum[j][l-1]+sum[i-1][l-1]>k) {
                    l++;
                }
                ans+=r-l+1;
            }
        }
    }
    cout<<ans;
    return 0;
}