题目链接
由于求的是某个区间，而且是矩形区间的和，所以想到用二维前缀数组求解。
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
| #include <bits/stdc++.h>
using namespace std;
int n, L, r, t;
int m[601][601];
int a[601][601];
int main() {
scanf("%d%d%d%d", &n, &L, &r, &t);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j)
scanf("%d", &m[i][j]);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + m[i][j];
}
}
int res = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
int x = min(n, i+r), y = min(n, j + r);
int xx = max(1, i - r), yy = max(1, j - r);
if(a[x][y] - a[xx-1][y] - a[x][yy-1] + a[xx-1][yy-1] <= (x-xx+1)*(y-yy+1) * t) res++;
}
}
cout << res;
return 0;
}
|
考试时候还不知道前缀数组，硬算只能得70分…
