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

ruiqi2012 · 2024-04-30 15:07:05 · 题解

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

好了，今天我们来看这道蓝桥杯的水题

80pts的朋友，十年oi一场空，不开long long见祖宗

身为蒟蒻的我都能A掉这道题，你说水不水？

没看题目的人戳这里 题目传送门

现在切入正题！！

这道题的题意大概就是给你一个N \times M的矩阵， 让你算出其中每个子矩阵的值，并统计其中有多少个子矩阵的值是<K的，数据范围1≤N,M≤500,0≤A_{i,j}≤1000,1≤K≤2.5×10^8 \space暴力的佩服你的勇气

既然要求的是子矩阵中所有数的和，我们很容易就能想到用二维前缀和解决此题，不会的去看一下“地毯”这个题 地毯

二维前缀和中，设当前这一位的横纵坐标分别为x，y 那么这一位的值就为s[x-1][y]+s[y][y-1]-s[x-1][y-1]+a[x][y] 接下来我们用三层for套一个while来枚举矩阵的左上和右下， 因为只要确定这两个地方，就可以确定矩阵的大小及位置

设当前矩阵的左上坐标为（x_1,y_1）,右下坐标为（x_2,y_2）,那么当前矩阵的值就是s[y_1][y_2]-s[x_1-1][y_2]-s[y_1][x_2-1]+s[x_1-1][x_2-1]

再与K进行比较就可以了

满分Code（带注释）

#include<bits/stdc++.h>
using namespace std;
int n,m,kk;
int a[510][510];
long long s[510][510];
long long sum = 0;//再次提醒：十年OI一场空，不开long long见祖宗 
int main(){
    scanf("%d%d%d",&n,&m,&kk);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    s[0][0] = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;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 k = 1,l = 1;l<=m;l++){
                while(k<=l&&s[j][l]-s[i-1][l]-s[j][k-1]+s[i-1][k-1]>kk){
                    k++;//统计大于K的格子个数 
                }
                sum+=l-k+1;//更新答案
            }
        }
    }
    cout<<sum<<endl;//输出结果 
    return 0;
}