题目描述

blablabla

样例

blablabla

算法1： 前缀和 + 暴力枚举

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

使用前缀和进行暴力枚举，枚举每个点为起点，和枚举每个点为终点。时间复杂度是 $O(n^4)$。
对于 $70\%$ 的数据，$N,M≤100$，大概为 $10^8$，可以通过；
对于 $100\%$ 的数据，$1≤N,M≤500$，大概为 $10^{10}$，部分会超时；
暴力大概可以获得 $70$% 的分数。

C++ 代码

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

long long a[502][502];

int 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];
            a[i][j] += a[i-1][j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            long long s = a[i][j], row = i, col = j, temp = a[i-1][j];
            while (s - temp <= k && row <= n)
            {
                while (s - temp <= k && col <= m)
                {
                    ans++;
                    col++;
                    s += a[row][col];
                    temp += a[i-1][col];
                }
                col = j;
                row++;
                temp = a[i-1][j];
                s = a[row][j];
            }
        }
    }
    cout << ans;
    return 0;
}

算法2： 前缀和 + 双指针滑动窗口

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

从枚举每个点转换为枚举每一列，以每一列为起点和终点，使用双指针滑动窗口思维;
用 $left$ 表示左边界，从 $1$ 开始，$right$ 表示右边界，也从 $1$ 开始，子矩阵和为 $s$;
当 $s≤k$ 时，子矩阵的个数为 $right - left + 1$ 个矩阵；
当 $s＞k$ 时， $left$ 就向右移动，一直移动到满足 $s≤k$ 的位置，当 $left$ 走到 $m$ 点时循环结束。
对于 $100\%$ 的数据，$1≤N,M≤500$，大概为 $10^8$，可以全部通过。

C++ 代码

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

long long a[502][502];

int 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];
            a[i][j] += a[i-1][j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            long long left = 1, right = 1, s = 0;
            while (right <= m)
            {
                s += a[j][right] - a[i-1][right];
                while (s > k)
                {
                    s -= a[j][left] - a[i-1][left];
                    left++;
                }
                ans += right++ - left + 1;
            }
        }
    }
    cout << ans;
    return 0;
}