HzuYZL

用户名：H2030819025

访问量：57577

签　名：

等　　级
排　　名	30
经　　验	14100
参赛次数	16
文章发表	25
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛真题-刷题统计
浏览：174

蓝桥杯2022年第十三届省赛真题-修剪灌木
浏览：287

蓝桥杯2018年第九届真题-日志统计(排序 + 双指针)
浏览：60

你可能喜欢

蓝桥杯2022年第十三届省赛真题-统计子矩阵(前缀和 + 双指针)

　　作者: HzuYZL　　　　发表时间：2023-03-25 22:53:15 浏览：690　|　评论：1　

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

####解题思路
1.求每列前缀和（i，j 为上下边界，则可看成用一维解决）。
2.用双指针 l， r 维护左右边界，当 r 边界确定时（找到了 sum > k 的区间），左边界 l 往右移寻找符合条件的区间。
![](/image_editor_upload/20230325/20230325102916_78584.png)
![](/image_editor_upload/20230325/20230325103127_71533.png)
3.符合区间求和
####参考代码
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int f[N][N];
int n, m, k;

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &f[i][j]),
            f[i][j] += f[i - 1][j]; // 计算每列前缀和
         
    long long res = 0;
    for (int i = 1; i <= n; i ++ ) // 上边界
        for (int j = i; j <= n; j ++ ) // 下边界
            for (int l = 1, r = 1, sum = 0; r <= m; r ++ )
            {
                sum += f[j][r] - f[i - 1][r]; // 确定右边界 r
                while (sum > k) // 求符合条件的左边界 l
                {
                    sum -= f[j][l] - f[i - 1][l];
                    l ++ ;
                }
                res += r - l + 1; 
            }
            
    cout << res;

return 0;
}
```

0.0分

10 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

LuckyChen

问问在while 那里需不需要添加一个&& l<=r;以保证当k太小的时候l一直加的情况

2024-04-06 14:59:55

HzuYZL

TA的其他文章

你可能喜欢

C二级辅导-公约公倍（C语言代码）

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

矩形面积交（Java代码）

C二级辅导-统计字符（C语言代码）

The 3n + 1 problem （C语言代码）

蓝桥杯2022年第十三届省赛真题-统计子矩阵(前缀和 + 双指针)

评论区

精彩推荐

人见人爱A+B （C语言代码）

简单的a+b （C语言代码）

【回文数(二)】（C++代码）

C二级辅导-统计字符（C语言代码）

拆分位数（C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

打印十字图（C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

HzuYZL

TA的其他文章

你可能喜欢

C二级辅导-公约公倍 （C语言代码）

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

矩形面积交 （Java代码）

C二级辅导-统计字符 （C语言代码）

The 3n + 1 problem （C语言代码）

蓝桥杯2022年第十三届省赛真题-统计子矩阵(前缀和 + 双指针)

评论区

精彩推荐

人见人爱A+B （C语言代码）

简单的a+b （C语言代码）

【回文数(二)】 （C++代码）

C二级辅导-统计字符 （C语言代码）

拆分位数 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

打印十字图 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C二级辅导-公约公倍（C语言代码）

矩形面积交（Java代码）

C二级辅导-统计字符（C语言代码）

　　评论区

【回文数(二)】（C++代码）

C二级辅导-统计字符（C语言代码）

拆分位数（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

打印十字图（C语言代码）