AcWing 4405. 统计子矩阵（双指针，前缀和）

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

输入格式
第一行包含三个整数 $N,M$ 和 $K$。

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

输出格式
一个整数代表答案。

数据范围
对于 $30$ 的数据，$N,M\le 20$，
对于 $70$ 的数据，$N,M\le 100$，
对于 $100$ 的数据，$1\le N,M\le 500;0\le Aij\le 1000;1\le K\le 2.5\times 10^8$。

输入样例：

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

输出样例：

19
1

样例解释

满足条件的子矩阵一共有 19，包含：

大小为 1×1 的有 10 个。
大小为 1×2 的有 3 个。
大小为 1×3 的有 2 个。
大小为 1×4 的有 1 个。
大小为 2×1 的有 3 个。
1
2
3
4
5
6
7

没想到同一道题，仅仅是隔了一天，再一次遇见就又不会写了，所以复习很重要。。

对于此题，时间限制为$1s$，而矩阵的行和列的范围为$0$到$500$，假如我们暴力枚举每一行每一列，就会有$500$的四次方的时间复杂度，肯定爆了，但是假如只枚举行，就会有$500$的平方的复杂度，再加上运用双指针来扫描列，时间复杂度就不会爆了。

那么可以在处理前缀和的时候仅处理列前缀和，也就是不再处理出整个矩阵的前缀和，因为我们要枚举行。

之后再使用双指针扫描列，比如使用$l$和$r$。

• 首先定义$l$和$r$为$1$（初始下标），然后每次循环以$r$为主线，让$r$自增
• 在循环中，首先处理出来$1$ ~ $r$列（在我们枚举的行的区间中）的总和，如果这个总和大于了$k，就让总和减去 $l$列的总和，然后让$l$往右走（因为这时候如果r在比较靠左的位置就已经大于k了，如果r再往右走，就也一定会大于$k$，那么就必须让$l$往右走），并且在一次加和大于$k$之后，每次$r$往右走，$l$都肯定要往右走，这里不需要进行判断或是什么。

代码：

#include
using namespace std;
const int N = 510;
#define ll long long
ll s[N][N];
int n, m, k;
int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
			s[i][j] += s[i - 1][j]; //处理列前缀和
		}
	}

	ll res = 0;
	for (int i = 1; i <= n; i++) {      //枚举行
		for (int j = i; j <= n; j++) {
			//注意这里sum定义到for里，因为在双指针扫描的过程中sum的值不能被初始化
			for (int l = 1, r = 1, sum = 0; r <= m; r++) {  
				sum += s[j][r] - s[i-1][r]; //先加上r列的总和
				while (sum > k) {           //如果超过了
					sum -= s[j][l] - s[i - 1][l];
					l++;   //在sum > k之后，每次r走，j必定走
				}

				res += r - l + 1;   //矩阵数量
			}
		}
	}
	cout << res;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33