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

题目描述

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

输入格式

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

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

输出格式

一个整数代表答案。

输入输出样例

输入 #1

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

输出 #1

19

说明/提示

【样例说明】

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

大小为 1×11×1 的有 1010 个。

大小为 1×21×2 的有 33 个。 大小为 1×31×3 的有 22 个。

大小为 1×41×4 的有 11 个。

大小为 2×12×1 的有 33 个。

【评测用例规模与约定】

对于 30% 的数据, N,M≤20.

对于 70% 的数据, N,M≤100.

对于 100% 的数据, 1≤N,M≤500,0≤Aij​≤1000,1≤K≤2.5×1e8.

蓝桥杯 2022 省赛 B 组 F 题。

看到要求矩阵和我们首先想到二位前缀和，先想出我们的暴力方法：首先预处理得出二位前缀和数组，然后枚举左上角，对每一个左上角都去枚举右下角，根据我们的前缀和方程求得当前这个矩阵的和值是多少，和我们的k值比较即可。当然这样肯定超时，我们可以很轻松的想出第一个优化：比如我枚举了右下角在第一行的矩阵之后，已经找到一个大于k值的矩阵，那么我第二行就不要再包括他了。我们可以设置一个随着枚举而更新的maxc记录这个值，这个方案可以大大缩短我们的程序运行时间，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
int a[505][505] = { 0 };
int s[505][505] = { 0 };
 
signed main()
{
    int n, m, k;cin >> n >> m >> k;
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            cin >> a[i][j];
            s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {//以上两个循环枚举左上角
            int maxc = m + 1;
            for (int r = i;r <= n;r++)
            {
                for (int c = j; c < maxc;c++)
                {//枚举右下角
                    if (s[r][c] - s[i - 1][c] - s[r][j - 1] + s[i - 1][j - 1] > k)
                    {
                        maxc = c;
                        break;
                    }
                    else ans++;
                }
            }
        }
    }
    cout << ans;
 
    return 0;
}

不过就算这样，还是有两个点过不了，只能拿80分。虽然是优化过的，但我们这个方法的本质依然是枚举左上角与右下角，复杂度还是太高：o(m^2*n^2)。第二个优化我是想不出来了，这也代表了我们这样用二位前缀和，只能拿部分分。

看了题解，了解到第二种方法，当然还是建立在前缀和的基础上：我们不在枚举左上角与右下角，而是转为枚举行的范围：这是一个o(n^2)的操作。然后我们使用一个双指针去遍历这个范围，就像是把二维问题降维成一维一样:   有一个序列 [1,3,4,3]，试求出其中有多少个子序列，满足该子序列的所有元素之和小于等于 10。具体思路参考：P8783 题解 - 洛谷专栏 (luogu.com.cn)

有一个需要解释的点，关于ans为什么等于r-l+1：比如一开始我们l是1，r是2，sum，也就是和值=3，小于我们的k值。此时我们就可以被r++，那么相应的，ans，也就是子矩阵（放在这里就是连续子序列的个数）增加了多少呢？方案从“1,2,12”变成了“1,2,3,12,23,123”，可以自己模拟一下，会发现原来的数列里所有以i(1<=i<x,x为当前增加的数)为开头，以原本的最后一位为结尾的方案都会作为新加入的数的方案之一(也就是上面例子的23和123，都是新方案)，再加上这个数本身， 就是r-l+1。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
int a[505][505] = { 0 };
int s[505][505] = { 0 };
 
signed main()
{
    int n, m, k;cin >> n >> m >> k;
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            cin >> a[i][j];
            s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++)
    {
        for (int j = i;j <= n;j++)
        {//以上两个循环枚举两条线
            int l, r;
            l = r = 1;
            while (r <= m)//双指针
            {
                if (s[j][r] - s[j][l - 1] - s[i - 1][r] + s[i - 1][l - 1] <= k)
                {
                    ans += r - l + 1;
                    r++;
                }
                else l++;
            }
 
        }
    }
    cout << ans;
 
    return 0;
}