当前位置:首页 » 《随便一记》 » 正文

4405. 统计子矩阵

10 人参与  2023年04月04日 10:31  分类 : 《随便一记》  评论

点击全文阅读


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

输入格式
第一行包含三个整数 N,M 和 K。

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

输出格式
一个整数代表答案。

数据范围
对于 30% 的数据,N,M≤20,
对于 70% 的数据,N,M≤100,
对于 100% 的数据,1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000。

输入样例:
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
输出样例:
19
样例解释
满足条件的子矩阵一共有 19,包含:

大小为 1×1 的有 10 个。
大小为 1×2 的有 3 个。
大小为 1×3 的有 2 个。
大小为 1×4 的有 1 个。
大小为 2×1 的有 3 个。

分析

此题就是二维前缀和 和 双指针,公式模板如下,可以画个方格图,每个方格就是一个点,就更清晰:
S[i, j] = 第i行j列格子左上部分所有元素的和 :a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
在这里插入图片描述

四层for暴力解法 O(N4)(70分)

枚举每个点为起点,和枚举每个点为终点,这样就可以得到所有的子矩阵(不重不漏),但时间复杂度是O(n^4),会超时;

#include <bits/stdc++.h>using namespace std;int n, m, k;int a[505][505];long long ans = 0;int main() {    cin >> n >> m >> k;    for (int i = 1; i <= n; ++i) {        for (int j = 1; j <= m; ++j) {            cin >> a[i][j];            //二维前缀和,第i行j列格子左上部分所有元素的和            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];        }    }    for (int i = 1; i <= n; ++i) {        for (int j = 1; j <= m; ++j) {            for (int l = i; l <= n; ++l) {                for (int p = j; p <= m; ++p) {                    //以(i, j)为左上角,(l, p)为右下角的子矩阵的和为:                    int sum = a[l][p] - a[l][j - 1] - a[i - 1][p] + a[i - 1][j - 1];                    if (sum <= k)                        ans++;                }            }        }    }    cout << ans;    return 0;}

双指针优化 O(N3)

i,j分别表示一个区域的左右边界,p,q来表示上下两个指针,p一开始在最上面,不断向下来找q,至到权值和小于等于k(而且不能越界也就是p>q),然后p q这片区域的行数q-p+1就是子矩阵的个数;
在这里插入图片描述

#include <bits/stdc++.h>using namespace std;int n, m, k;int a[505][505];long long ans = 0;int main() {    //ios::sync_with_stdio(false);    //cin >> n >> m >> k;    scanf("%d%d%d", &n, &m, &k);    for (int i = 1; i <= n; ++i) {        for (int j = 1; j <= m; ++j) {            scanf("%d", &a[i][j]);            //二维前缀和,第i行j列格子左上部分所有元素的和            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];        }    }    for (int i = 1; i <= m; ++i) {        for (int j = i; j <= m; ++j) {            for (int p = 1, q = 1; q <= n; ++q) {                while (p <= q && a[q][j] - a[q][i - 1] - a[p - 1][j] + a[p - 1][i - 1] > k) {                    //一直让p指针下移到权值和<=k                    p++;                }                if (p <= q) {                    //在当前i,j的情况下,此时p q 之间的所有子矩阵都满足条件,一共q-p+1行                    ans += (q - p + 1);                }            }        }    }    cout << ans;    return 0;}

点击全文阅读


本文链接:http://zhangshiyu.com/post/58288.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 你要战功我给你,妖兽入侵你哭啥高质量好文叶天凌筱完本_你要战功我给你,妖兽入侵你哭啥高质量好文(叶天凌筱)
  • 夫君和小三霸占了我的将军府,我杀疯了阅读_雪儿谭绍木兰全集_小说后续在线阅读_无删减免费完结_
  • 鹿溪小说(鹿溪)终章+番外(穿进恐怖游戏后,我和反派HE了)一口气阅读
  • 完结文留给儿子的副卡月月刷爆,他却因睡桥底被送进收容所列表_完结文留给儿子的副卡月月刷爆,他却因睡桥底被送进收容所(娄墨霆宋佑轩)
  • 你活着,却死在我等你的第三年后续+番外_谨言佳佳温以宁全集_小说后续在线阅读_无删减免费完结_
  • 相思溺于夏时雨小说(裴景澈初念可)章节目录+起始篇章(相思溺于夏时雨)全章无套路在线
  • 未婚夫重生归来叫停手术,把剥开肚子的我困在手术台上40分钟(裴临渊阮离歌)
  • 完结文离婚是你提,净身出户你又哭什么精彩分享列表_完结文离婚是你提,净身出户你又哭什么精彩分享(苏铭余素伊)
  • 全书浏览哥哥重生救我,我带队灭了组织!(陈致远陈知韫)_哥哥重生救我,我带队灭了组织!(陈致远陈知韫)全书结局
  • 全文算命赚功德,我直接飞升成仙(楚天河林风)列表_全文算命赚功德,我直接飞升成仙
  • 八零丈夫抛妻弃子后悔不当初完整文本_顾尧全文_小说后续在线阅读_无删减免费完结_
  • 殉情三年,侯门主母休夫日百棺开道附加(殉情三年,侯门主母休夫日百棺开道)(沈宁鸢谢挽舟)全本浏览阅读连载中

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1