许健跃

用户名：Kazimierz

访问量：3255

签　名：

等　　级
排　　名	3276
经　　验	1976
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	长江大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛-统计子矩阵(前缀和暴力 and 双指针优化)
浏览：979

K-进制数(简简单单写个dfs)
浏览：120

K-进制数(排列组合解)
浏览：685

你可能喜欢

蓝桥杯2022年第十三届省赛-统计子矩阵(前缀和暴力 and 双指针优化)

　　作者: 许健跃　　　　发表时间：2022-09-05 17:56:50 浏览：979　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-统计子矩阵

## 1.暴力解法--二维前缀和（只能过70%）
```
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 505;
int s[N][N],n,m;
LL res,k;

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
        }

for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int l=1;l<=m;l++)
                for(int r=l;r<=m;r++)
                {
                    LL sum = s[j][r] - s[i-1][r] - s[j][l-1] + s[i-1][l-1];
                    if(sum<=k) res++;
                }
    cout<<res<<endl;
    return 0;
}
```
## 2.前缀和+双指针优化（过100%）
```
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 505;
int s[N][N],n,m;
LL res,k;

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>s[i][j];
            s[i][j] += s[i-1][j]; //预处理每一列前缀和
        }
    
    for(int i=0;i<n;i++)
        for(int j=i;j<n;j++)
            for(LL r=0,l=0,sum=0;r<m;r++)
            {
                sum += s[j][r] - s[i-1][r];
                while(sum>k)
                {
                    sum -= s[j][l] - s[i-1][l];
                    l++;
                }
                res += r - l + 1;
            }
    cout<<res<<endl;
    return 0;
}
```

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

许健跃

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

【计算直线的交点数】（C语言代码）

【蟠桃记】（C++代码）（递归计算）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

蓝桥杯2022年第十三届省赛-统计子矩阵(前缀和暴力 and 双指针优化)

评论区

精彩推荐

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

矩形面积交（Java代码）

分糖果（C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-复数求和（C++代码）

printf基础练习2 （C语言代码）

【蟠桃记】（C语言代码）

许健跃

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

【计算直线的交点数】 （C语言代码）

【蟠桃记】 （C++代码）（递归计算）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

蓝桥杯2022年第十三届省赛-统计子矩阵(前缀和暴力 and 双指针优化)

评论区

精彩推荐

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

矩形面积交 （Java代码）

分糖果 （C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-复数求和 （C++代码）

printf基础练习2 （C语言代码）

【蟠桃记】 （C语言代码）

【计算直线的交点数】（C语言代码）

【蟠桃记】（C++代码）（递归计算）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

母牛的故事（C语言代码）

矩形面积交（Java代码）

分糖果（C++代码）

WU-复数求和（C++代码）

【蟠桃记】（C语言代码）