每日一题第五十七期洛谷统计子矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了每日一题第五十七期洛谷统计子矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

题目描述

给定一个 $\times M$ 的矩阵 $A$ ，请你统计有多少个子矩阵 (最小 $\times 1$ , 最大 $\times M)$ 满足子矩阵中所有数的和不超过给定的整数 $K$ 。

输入格式

第一行包含三个整数 $N, M$ 和 $K$ 。

之后 $N$ 行每行包含 $M$ 个整数, 代表矩阵 $A$ 。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例说明】

满足条件的子矩阵一共有 $19$ ，包含:

大小为 $\times 1$ 的有 $10$ 个。

大小为 $\times 2$ 的有 $3$ 个。大小为 $\times 3$ 的有 $2$ 个。

大小为 $\times 4$ 的有 $1$ 个。

大小为 $\times 1$ 的有 $3$ 个。

【评测用例规模与约定】

对于 $\%$ 的数据, $\leq 20$ .

对于 $\%$ 的数据, $\leq 100$ .

对于 $\%$ 的数据, $\leq N, M \leq 500,0 \leq A_{i j} \leq 1000,1 \leq K \leq 2.5\times10^8$ .

蓝桥杯 2022 省赛 B 组 F 题。文章来源地址https://www.toymoban.com/news/detail-856069.html

AC代码：

#include<iostream>

using namespace std;

typedef long long ll;
const int N = 510;
ll a[N][N];
ll n, m, k;
ll sum[N][N];
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> sum[i][j];
            sum[i][j] += sum[i - 1][j]; 
        }
    }
    ll res = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i; j <= n; j ++)
        {
            for(ll l = 1, r = 1, s = 0; r <= m; r ++)
            {
                s += sum[j][r] - sum[i - 1][r];
                while(s > k)
                {
                    s -= sum[j][l] - sum[i - 1][l];
                    l ++;
                }
                res += r - l + 1;
            }
        }
    }
    cout << res << endl;
    return 0;
}