P8783统计子矩阵题解

xhl_leo · 2024-05-02 20:04:31 · 题解

没瞅题面就瞎康题解的人(如某些抄题解的)往这里康：

题目传送门

题目大意

给定一个n×m 的矩阵，求其中有多少个子矩阵的所有元素之和小于等于k。

30分蒟蒻之蒟蒻做法

首先，暴力这种万能(TLE和MLE,RE忽略不计)的方法肯定是有的,枚举每一个矩阵，遍历矩阵求和来判断是否大于k,但我们做题TLE和MLE,RE是忽略不了的，所以暴力只能满足得分的需求，想AC的话就不行了，今不予供出代码。

80分蒟蒻做法

提到矩阵求和，我立马想到用二维前缀和(不会用前缀和的先康前缀和+差分+离散化+区间合并,题单 前缀和、差分与离散化和billbill。)，枚举左上角和右下角求和，判断是否大于k,但时间复杂度还是O(N_2M_2)，只能得80分(听说有卡过的)，但也很好了，得分状况如下： 80分代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=666;
int n,m,k,h;
int a[N][N],s[N][N];
signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%lld",&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 l=1;l<=i;l++){
                for(int r=1;r<=j;r++){//枚举左上角和右下角 
                    if(s[i][j]-s[l-1][j]-s[i][r-1]+s[l-1][r-1]<=k){//符合条件，记录下来 
                        h++;
                    }
                }
            }
        }
    } 
    printf("%lld",h);
    return 0;
}

100分大佬做法

在80分的代码的基础上，我们只需进行亿点点优化，就能出现奇迹。方法是判断到一个矩阵和大于k,接下来就不用枚举了。为什么这么说，我们都知道,假如区间[3,6]的和大于k,那么区间[3,7]的和和区间[4,6]的和也一定大于k。 由此猜想，假如蓝框矩阵和大于k,那么红框矩阵和也一定大于k。 于是我们就能看出来，这是一个二维框取。符合矩阵的条件，并且矩阵和小于等于k,l就加一。 再把判断和for循环融合成一个while循环，即可AC最后两个点。 100分代码如下(不建议复制)：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=666;
int n,m,k,h,a[N][N],s[N][N];
signed main() {
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%lld",&a[i][j]);
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];//与80分代码相同 
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=i; j<=n; j++) {
            for(int l=1,r=1; r<=m; r++) {
                while(l<=r&&s[j][r]-s[i-1][r]-s[j][l-1]+s[i-1][l-1]>k) {//判断是否符合矩阵的条件，并且矩阵和小于等于K 
                    l++;
                }
                h+=r-l+1;//计入答案
            }
        }
    }
    printf("%lld",h);
    return 0;
}