题目描述
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;
}