跳转至

202104-2 邻域均值

70% 数据——直接模拟

按照题目要求，算出每个点的邻域均值，然后直接统计即可。

一共有 \(\mathrm{O}(n^2)\) 个点，每个点统计复杂度 \(\mathrm{O}(r^2)\)，整体复杂度 \(\mathrm{O}(n^2r^2)\)。

100% 数据——由相邻邻域均值推导

为了简化说明及避免除法精度问题，我们可以将邻域均值是否小于等于 \(t\) 转化为邻域值的总和是否小于等于 \(t\) 与元素合数之积。

考虑在 70 分的做法中什么地方浪费了时间：在统计完一个点的邻域值的总和时，我们就抛弃了这个点的信息，完全重新计算其他点的邻域值的和。但对于相邻的点，其邻域有很大面积的重合，最多相差 \(2r\) 个元素。

在原本的基础上，只需要处理这 \(2r\) 个元素的更改即可。

考虑时间复杂度：算出第一个点的邻域值的和为 \(\mathrm{O}(r^2)\)，一共要进行 \(n^2\) 次 \(\mathrm{O}(r)\) 的修改，整体比较复杂度 \(n^2\)，最终复杂度 \(\mathrm{O}(r^2+n^2r)\)。

代码实现
 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 610;
int n, L, r, t;
int a[maxn][maxn], sum[maxn][maxn];
int ans;
inline int getSum(int row1, int col1, int row2, int col2) {
    // 计算一块矩阵区间的和
    int res = 0;
    for (int i = row1; i <= row2; ++i) {
        for (int j = col1; j <= col2; ++j) {
            res += a[i][j];
        }
    }
    return res;
}
inline int getSize(int x, int y) {
    // 计算 (x,y) 的邻域大小
    int row1 = max(x - r, 1), col1 = max(y - r, 1);
    int row2 = min(x + r, n), col2 = min(y + r, n);
    return (row2 - row1 + 1) * (col2 - col1 + 1);
}
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", &a[i][j]);
        }
    }

    // 求出 sum[1][1]
    sum[1][1] = getSum(1, 1, min(r + 1, n), min(r + 1, n));
    // 求出 sum[1][2..n]
    for (int j = 2; j <= n; ++j) {
        sum[1][j] = sum[1][j - 1];
        // 减去最左侧一部分
        if (j - 1 - r > 0)
            sum[1][j] -= getSum(1, j - 1 - r, min(r + 1, n), j - 1 - r);
        // 增加右侧一部分
        if (j + r <= n)
            sum[1][j] += getSum(1, j + r, min(r + 1, n), j + r);
    }

    // 计算剩下部分，sum[i][j] 由 sum[i-1][j] 转移而来
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            sum[i][j] = sum[i - 1][j];
            if (i - 1 - r > 0)
                sum[i][j] -=
                    getSum(i - 1 - r, max(j - r, 1), i - 1 - r, min(j + r, n));
            if (i + r <= n)
                sum[i][j] += getSum(i + r, max(j - r, 1), i + r, min(j + r, n));
        }
    }

    // 统计答案
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (sum[i][j] <= t * getSize(i, j))
                ++ans;
        }
    }
    printf("%d", ans);
    return 0;
}

100% 数据——二维前缀和

对于多次询问一段区间的值，容易想到前缀和；如果多次询问二维区间的值，需要二维前缀和。

设 \(S(x,y)= \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}{a_{i,j}}\)，则 \((x_1,y_1)\) 到 \((x_2,y_2)\) （\(x_2\ge x_1, y_2\ge y_1\)）的和可以表示为：

\[S(x_2,y_2) - S(x_1 - 1, y_2) - S(x_2, y_1 - 1) + S(x_1 - 1, y_1 - 1)\]

我们可以 \(\mathrm{O}(n^2)\) 预处理出 \(S(x,y)\) 数组，之后则可以 \(\mathrm{O}(1)\) 查询单点邻域值的和了。总体时间复杂度 \(\mathrm{O}(n^2)\)。

代码实现
 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
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 610;
int n, L, r, t;
int a[maxn][maxn], sum[maxn][maxn];
int ans;
inline int getSize(int x, int y) {
    // 计算 (x,y) 的邻域大小
    int row1 = max(x - r, 1), col1 = max(y - r, 1);
    int row2 = min(x + r, n), col2 = min(y + r, n);
    return (row2 - row1 + 1) * (col2 - col1 + 1);
}
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", &a[i][j]);
        }
    }

    // 预处理前缀和数组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            sum[i][j] =
                sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }

    // 统计答案
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int row1 = max(1, i - r), col1 = max(1, j - r);
            int row2 = min(n, i + r), col2 = min(n, j + r);
            int s = sum[row2][col2] - sum[row2][col1 - 1] -
                    sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1];
            if (s <= t * getSize(i, j))
                ++ans;
        }
    }
    printf("%d", ans);
    return 0;
}

评论