第十三届蓝桥杯 C++ B 组省赛 F 题——统计子矩阵（AC）

骑猪看日落 2023-09-28 23:36 19阅读 0赞

## 1.统计子矩阵 ##

### 1.题目描述 ###

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

### 2.输入格式 ###

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

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

### 3.输出格式 ###

一个整数代表答案。

### 4.样例输入 ###

3 4 10  
1 2 3 4  
5 6 7 8  
9 10 11 12

### 5.样例输出 ###

### 6.数据范围 ###

1 ≤ N , M ≤ 500 ; 0 ≤ A i j ≤ 1000 ; 1 ≤ K ≤ 250000000. 1≤N,M≤500;0≤Aij ≤1000;1≤K≤250000000. 1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000.

### 7.原题链接 ###

[统计子矩阵][Link 1]

## 2.解题思路 ##

首先，我们有一个查询子矩阵和的需求，这肯定是需要使用预处理二维前缀和来优化查询的。  
未学习过的请跳转： [二维前缀和][Link 2]  
但确定一个子矩阵，需要一个左上角坐标 ( x 1 , y 1 ) (x1,y1) (x1,y1)和一个右下角坐标 ( x 2 , y 2 ) (x2,y2) (x2,y2)，如果进行暴力枚举的话复杂度将会是 O ( n 4 ) O(n^4) O(n4)，这不可取。  
考虑如何进行优化，对于  x 1 x1 x1 和  x 2 x2 x2 我们仍然进行暴力枚举。 然后考虑如何确定 y 1 y1 y1和 y 2 y2 y2，这里我们用 L L L表示 y 1 y1 y1，用  R R R 表示  y 2 y2 y2。  
由于数组内不存在负数，不难发现**随着指针 R R R右移， L L L也一定单调向右移动**，这就转化成了一个一维数组内求子数组和不大与  K K K 的数目问题。枚举 R R R为右边界，此时子矩阵左上角坐标为 ( x 1 , L ) (x1,L) (x1,L)，右下角坐标为 ( x 2 , R ) (x2,R) (x2,R)，如求得总和大于  K K K ， L L L 向右移动，统计当前  R R R 作为右边界的答案数量为  R − L + 1 R-L+1 R−L\+1，这样双指针的做法复杂度为 O ( n ) O(n) O(n)。当然也可以二分得到  L L L 的位置，但是复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。  
这样使用双指针整体的复杂度为 O ( n 3 ) O(n^3) O(n3)，如果使用二分的话为 O ( n 3 l o g n ) O(n^3logn) O(n3logn)会超时。 O ( n 3 ) O(n^3) O(n3)的复杂度在`500`下计算次数就达到了`500x500x500=125,000,000`。  
我们来分析一下为什么双指针能过但二分不能过，因为枚举  x 1 x1 x1 和  x 2 x2 x2 的操作严格意义的复杂度应该是 O ( n 2 2 ) O(\\frac \{n^2 \}\{2\}) O(2n2)，所以双指针算法实际运算次数应该是`125,000,000/2=62,500,000`是可以过的。二分会再乘一个  l o g 500 log500 log500，那肯定就爆掉了，经测试也二分做法也确实挂掉了。两个代码我都贴上  
![在这里插入图片描述][cfa048af19e54b179ef292f6e0c36406.png]

## 3.Ac\_code ##

**前缀和+双指针**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair<int, int> PII;
    #define pb(s) push_back(s);
    #define SZ(s) ((int)s.size());
    #define ms(s,x) memset(s, x, sizeof(s))
    #define all(s) s.begin(),s.end()
    const int inf = 0x3f3f3f3f;
    const int mod = 1000000007;
    const int N = 510;
    
    LL n, m, k;
    LL a[N][N], s[N][N];
    //求子矩阵的和
    LL sum(int x1, int y1, int x2, int y2) {
        
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    }
    void solve()
    {
        
        cin >> n >> m >> k;
        for (int i = 1; i <= n; ++i) {
        
            for (int j = 1; j <= m; ++j) {
        
                cin >> a[i][j];
            }
        }
        for (int i = 1; i <= n; ++i) {
        
            for (int j = 1; j <= m; ++j) {
        
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
            }
        }
        LL ans = 0;
        for (int i = 1; i <= n; ++i) {
        
            for (int j = i; j <= n; ++j) {
        
                for (int l = 1, r = 1; r <= m; ++r) {
        
                    while (l <= r && sum(i, l, j, r) > k) l++;
                    ans += r - l + 1;
                }
            }
        }
        cout << ans << '\n';
    }
    
    int main()
    {
        
        ios_base :: sync_with_stdio(false);
        cin.tie(nullptr);
        int t = 1;
        while (t--)
        {
        
            solve();
        }
        return 0;
    }

**前缀和+二分（过80%数据）**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair<int, int> PII;
    #define pb(s) push_back(s);
    #define SZ(s) ((int)s.size());
    #define ms(s,x) memset(s, x, sizeof(s))
    #define all(s) s.begin(),s.end()
    const int inf = 0x3f3f3f3f;
    const int mod = 1000000007;
    const int N = 510;
    
    LL n, m, k;
    LL a[N][N], s[N][N];
    //求子矩阵的和
    LL sum(int x1, int y1, int x2, int y2) {
        
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    }
    void solve()
    {
        
        cin >> n >> m >> k;
        for (int i = 1; i <= n; ++i) {
        
            for (int j = 1; j <= m; ++j) {
        
                cin >> a[i][j];
            }
        }
        for (int i = 1; i <= n; ++i) {
        
            for (int j = 1; j <= m; ++j) {
        
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
            }
        }
        LL ans = 0;
        for (int i = 1; i <= n; ++i) {
        
            for (int j = i; j <= n; ++j) {
        
                for (int t = 1; t <= m; ++t) {
        
                    int l = 1, r = t;
                    while (l < r) {
        
                        int mid = l + r >> 1;
                        if (sum(i, mid, j, t) > k) l = mid + 1;
                        else r = mid;
                    }
                    if (sum(i, l, j, t)<=k) ans += t - l + 1;
                }
            }
        }
        cout << ans << '\n';
    }
    
    int main()
    {
        
        ios_base :: sync_with_stdio(false);
        cin.tie(nullptr);
        int t = 1;
        while (t--)
        {
        
            solve();
        }
        return 0;
    }

[Link 1]: https://www.lanqiao.cn/problems/2109/learning/
[Link 2]: https://blog.csdn.net/m0_57487901/article/details/124682059
[cfa048af19e54b179ef292f6e0c36406.png]: https://img-blog.csdnimg.cn/cfa048af19e54b179ef292f6e0c36406.png