这道题又是前缀和,只不过是二维的,突然发现csp第二题好喜欢前缀和啊。
由于矩阵不小,如果对于每一个点,我们都去遍历一遍算平均值,必定超时且麻烦。
不如应用一下前缀和思想,很快能计算出某一区域的总和,然后我们拿他去和这个区域的个数乘阈值相比,小于等于就增加计数器就好了。
现在问题变成了每一个点对应的区域是什么,因为有的点在边界,区域内点数不固定,那我们就重新计算x1,x2,y1,y2。这个区域就有了。
- #include
- using namespace std;
- typedef long long LL;
- const int N = 700;
- int a[N][N];
- int main() {
- int n, L, r, t;
- cin >> n >> L >> r >> t;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- scanf("%d", &a[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];
- //前缀和的计算
- int sum = 0;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- int x1 = max(1, i - r);//判断是否超出边界,超出的话,就用边界
- int x2 = min(n, i + r);
- int y1 = max(1, j - r);
- int y2 = min(n, j + r);
- LL num = a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
- LL num2 = (x2 - x1 + 1) * (y2 - y1 + 1) * t;
- if (num <= num2)sum++;
- }
- }
- cout << sum;
- return 0;
- }