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

执梗

10630人浏览 · 2022-11-22 12:40:58

执梗 · 2022-11-22 12:40:58 发布

1.统计子矩阵

1.题目描述

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

2.输入格式

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

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

3.输出格式

一个整数代表答案。

4.样例输入

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

5.样例输出

6.数据范围

$1 \leq N, M \leq 500; 0 \leq A ij \leq 1000; 1 \leq K \leq 250000000.$

7.原题链接

统计子矩阵

2.解题思路

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

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