AcWing 4405. 统计子矩阵(蓝桥杯13届（2022）B组)    原题链接    中等

作者： 作者的头像   L-China ,  2023-03-23 18:26:12 ,  所有人可见 ,  阅读 2613

39


10

C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

70分：

思路：

二维前缀和

$通过二维前缀和处理一下每个子矩阵，然后4重循环枚举每个子矩阵，符合则res++$

$时间复杂度：O(n^4)$

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
typedef long long ll;

int n, m, k;
int s[N][N];

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];
        }

    ll res = 0;
    for (int x1 = 1; x1 <= n; x1 ++)
        for (int y1 = 1; y1 <= m; y1 ++)
            for (int x2 = x1; x2 <= n; x2 ++)
                for (int y2 = y1; y2 <= m; y2 ++) {
                    if (s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] <= k)
                    res ++;
                }
    cout << res;            
    return 0;
}

100（满分）

思路：

一维前缀和 双指针

$1、将列看成一个整体$

$2、i, j 枚举列的上下边界，通过双指针l, r维护列的左右边界$

$3、sum存储枚举列的和，如果大于sum>k了，列的左边界l++，直到sum<=k$

$4、res记录一下从l到r这一段列的贡献：r-l+1$

$时间复杂度：O(n^3)$

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
typedef long long ll;

int n, m, k;
int s[N][N];

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]; // 每列上的一维前缀和
        }

    ll res = 0;
    for (int i = 1; i <= n; i ++) // i j 上下边界
        for (int j = i; j <= n; j ++)
            for (int l = 1, r = 1, sum = 0; r <= m; r ++) { // l 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;        
    return 0;
}

16 评论

用户头像
Eilene   10个月前      6    踩      回复

res+=r-l+1;
//r是不断循环变化的，每更新一次r又经while循环后符合条件的带r列的矩形，就是r-l+1个
//0 1 2，带二的一维矩形分别是 012，12，2

用户头像
阿盈   9个月前         踩      回复

终于懂啦，感谢佬！！

用户头像
所念皆星河1   2023-04-06 23:25      2    踩      回复 
#include<iostream>
using namespace std;
const int N=510;//我能想到的就是暴力枚举+二维前缀和了。。
long long sum[N][N];//一旦涉及到什么前缀和用long long稳一手
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,kk;
    cin>>n>>m>>kk;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
        }
    }
//先写出朴素做法，500^4超时，只能过六个用例，放在比赛必然是赚的，思路易懂好写，但补题可不一样呀
//  for(int a=1;a<=n;a++){
//      for(int b=1;b<=m;b++){
//          for(int c=a;c<=n;c++){
//              for(int d=b;d<=m;d++){
//                  int res=sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1];
//                  if(res<=k) ans++;
//              }
//          }
//      }
//  }
    //将四维优化成三维，反正是要枚举子矩阵，i,j枚举上下界，right枚举右边界，左边界left可以根据区域和不大于k来约束，优化至三维
    long long ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int left=1;
            long long s;//求的是0~right这一小段长条的区域和
            long long ss;//求的是0~left-1这一小段长条的区域和
            for(int k=1;k<=m;k++){
                s=sum[j][k]-sum[i-1][k];
                ss=sum[j][left-1]-sum[i-1][left-1];
                //s-ss就是left~k的区域和呀
                if(s-ss<=kk){
                    ans+=k-left+1;
                }else{
                    while(s-ss>kk&&left<=k){
                        left++;
                        ss=sum[j][left-1]-sum[i-1][left-1];
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

一样的思路，只不过你是累和记录区间的值，我是直接利用二位前缀和得出，不用每次加加减减总和，而是可以一步求出，但是我不知道为什么过不了样例，求指点

用户头像
L-China   2023-04-07 12:25      1    踩      回复

看代码：

#include<iostream>
using namespace std;
const int N=510;//我能想到的就是暴力枚举+二维前缀和了。。
long long sum[N][N];//一旦涉及到什么前缀和用long long稳一手
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,kk;
    cin>>n>>m>>kk;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
        }
    }
//先写出朴素做法，500^4超时，只能过六个用例，放在比赛必然是赚的，思路易懂好写，但补题可不一样呀
//  for(int a=1;a<=n;a++){
//      for(int b=1;b<=m;b++){
//          for(int c=a;c<=n;c++){
//              for(int d=b;d<=m;d++){
//                  int res=sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1];
//                  if(res<=k) ans++;
//              }
//          }
//      }
//  }
    //将四维优化成三维，反正是要枚举子矩阵，i,j枚举上下界，right枚举右边界，左边界left可以根据区域和不大于k来约束，优化至三维
    long long ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int left=1;
            long long s;//求的是0~right这一小段长条的区域和
            long long ss;//求的是0~left-1这一小段长条的区域和
            for(int k=1;k<=m;k++){
                s=sum[j][k]-sum[i-1][k];
                ss=sum[j][left-1]-sum[i-1][left-1];
                //s-ss就是left~k的区域和呀
                if(s-ss<=kk){
                    ans+=k-left+1;
                }else{
                    while(s-ss>kk&&left<=k){
                        left++;
                        ss=sum[j][left-1]-sum[i-1][left-1];
                    }
                    ans+=k-left+1; 
                    /*
                    忘记记录当 s - ss > k 时，重新更新左边界left的值直到符合 s- ss <= k 
                    这一段的贡献了
                    */
                }
            }
        }
    }
    cout<<ans;
    return 0;
}
用户头像
所念皆星河1   2023-04-07 14:07    回复了 L-China 的评论      1    踩      回复

多谢兄弟，昨天把if判断删了然后过了我就反应过来了，害真不知道说什么好，感觉不应该出这种问题，又感觉出了这种问题活该。。

用户头像
还举着手机   10个月前      1    踩      回复

为什么从l到r贡献了(r-l+1)个？

用户头像
chanxe   2023-05-28 11:18      1    踩      回复 
n, m, k = map(int, input().split())

a = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1) :
    a[i][1 : m + 1] = list(map(int, input().split()))
    for j in range(1, m + 1) :
        a[i][j] = a[i][j] + a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1]
ans = 0
for i in range(1, n + 1) : # 上边界
    for j in range(i, n + 1) : # 下边界
        f = [0] * (m + 7)
        for r in range(1, m + 1) : # 列
            f[r] = a[j][r] - a[i - 1][r] # i~j行r列的前缀和
            l = r
            while l :
                s = f[r] - f[l - 1]
                if s <= k :
                    ans += 1
                else :
                    break
                l -= 1
print(ans)

看我Python来也

用户头像
L-China   2023-05-28 15:31         踩      回复

orzzzzzz

用户头像
人间小甜瓜   2023-06-01 14:36      1    踩      回复 
n, m, k = map(int, input().split())

a = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1) :
    a[i][1 : m + 1] = list(map(int, input().split()))
    for j in range(1, m + 1) :
        a[i][j] = a[i][j] + a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1]
ans = 0
for i in range(1, n + 1) : # 上边界
    for j in range(i, n + 1) : # 下边界
        f = [0] * (m + 7)
        l = 1
        for r in range(1, m + 1) : # 列
            f[r] = a[j][r] - a[i - 1][r] # i~j行l列的前缀和
            while l <= r and f[r] - f[l - 1] > k:
                l += 1
            ans += r - l + 1

print(ans)
用户头像
L-China   2023-06-01 23:16    回复了 人间小甜瓜 的评论         踩      回复

tpllllllllllll

用户头像
Flechazo1   9个月前         踩      回复

sum += s[j][r] - s[i - 1][r];这里看不懂

用户头像
何予   9个月前         踩      回复

大佬们，时间复杂度怎么算啊，三重for，r，l，最坏不是二者都到m吗？还是o(n^4)？不会算😓

用户头像
阿哈的艰难学习   10个月前         踩      回复

想了挺久，终于想到了

用户头像
đł_0   10个月前         踩      回复

请问这条while里面的这条语句为什么这么写
sum -= s[j][l] - s[i - 1][l];

用户头像
bitianan   10个月前         踩      回复

因为sum大了，要减小，所以 l 要+ +,s[j][l]-s[i-1][l]就是求i-j中 第l 列的总和

用户头像
小猫沾水   10个月前         踩      回复

感谢大佬，讲的好好！学会了