蓝桥杯2022年第十三届省赛真题-统计子矩阵 预处理+双指针

解题思路：

先进行预处理，把每一列矩阵进行压缩，即a[i][j]等于原矩阵第j列第1行到第i行的和。

三层for循环，第一层枚举子矩阵的起始行b，第二层枚举子矩阵的终点行i，第三层枚举子矩阵的终点列r。

起始列l初始为1，如果当前和超过了k，则使起始列l自增1，直到当前和不大于k。

答案数量每次加循环r-l+1。即当前起始行b、结束行i的情况下，以r为结束列的，和不大于k的子矩阵数量。

参考代码（C++）：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef unsigned long long ull;
const int maxn = 510;
const int INF = 0x3fffffff;
int n, m, k, a[maxn][maxn]; // a维护每列的前缀和

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            a[i][j] += a[i - 1][j];  // 将每一列的和压缩
        }
    }
    int ans = 0;
    for (int b = 1; b <= n; b++)  // 枚举子矩阵起始行
    {  
        for (int i = b; i <= n; i++)  // 枚举子矩阵终点行
        {
            int s = 0;
            for (int r = 1, l = 1; r <= m; r++)  // 枚举子矩阵结束列
            {
                s += a[i][r] - a[b - 1][r];
                while(s > k)
                {
                    s -= a[i][l] - a[b - 1][l];
                    l++;
                }
                ans += r - l + 1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}