【CSP试题回顾】202104-2-邻域均值

CSP-202104-2-邻域均值

关键点：二维差分数组

详见：【CSP考点回顾】差分数组

解题思路

初始化矩阵和参数：首先，代码接收矩阵的大小（n x n），每个元素的亮度值（位于[0, L]区间），以及算法特定的其他参数（r 和 t）。
计算前缀和矩阵：使用前缀和技术创建一个新矩阵（prefixSum），用于快速计算任何子矩阵的元素总和。前缀和矩阵的每个元素代表从原始矩阵左上角到当前位置的元素总和。
遍历原始矩阵：对每个元素，计算它的"邻域"内的元素总和。邻域定义为以当前元素为中心，边长为(2r + 1)的方阵区域（或边界内的实际区域）。
计算邻域内元素的平均亮度：使用前缀和矩阵快速计算邻域内的元素总和，并除以邻域内的元素数量，得到平均亮度。
判断元素是否为"暗"元素：如果邻域内的平均亮度小于等于阈值t，则该元素被认为是"暗"的。

差分数组和时间复杂度优化：

在未使用差分数组或前缀和技术时，直接计算每个元素的邻域内元素总和需要O(r^2)的时间（对于每个元素都要计算它邻域内的元素和，邻域大小约为 $2r + 1)^2$ ）。由于这需要对矩阵中的每个元素重复进行，总的时间复杂度将是 $O(n^2r^2)$ 。
使用差分数组或前缀和技术后，我们可以将任何子矩阵的元素总和的计算时间降低到 $O (1)$ （只需四次数组查找和三次加减运算）。因此，总的时间复杂度降低为 $O(n^2)$ （因为每个元素计算其邻域的总和变为常数时间）。这是通过提前计算所有可能子矩阵的元素和（即计算前缀和矩阵）实现的，从而在实际需要时可以立即获得任何特定邻域的总和。

完整代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, L, r, t;

// 计算前缀和矩阵
void computePrefixSum(vector<vector<int>>& ps, const vector<vector<int>>& a) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ps[i + 1][j + 1] = a[i][j] + ps[i + 1][j] + ps[i][j + 1] - ps[i][j];
        }
    }
}

// 计算(x1, y1)到(x2, y2)区域内的元素总和
int regionSum(const vector<vector<int>>& ps, int x1, int y1, int x2, int y2) {
    return ps[x2 + 1][y2 + 1] - ps[x2 + 1][y1] - ps[x1][y2 + 1] + ps[x1][y1];
}

int main() {
    cin >> n >> L >> r >> t;
    vector<vector<int>> matrixA(n, vector<int>(n));
    vector<vector<int>> prefixSum(n + 1, vector<int>(n + 1, 0));
    for (auto& it : matrixA) {
        for (auto& jt : it) {
            cin >> jt;
        }
    }

    computePrefixSum(prefixSum, matrixA);

    int darkNum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 计算当前元素的邻域边界
            int xStart = max(0, i - r), yStart = max(0, j - r);
            int xEnd = min(n - 1, i + r), yEnd = min(n - 1, j + r);
            int area = (xEnd - xStart + 1) * (yEnd - yStart + 1);
            // 使用前缀和计算邻域内的元素总和
            int sum = regionSum(prefixSum, xStart, yStart, xEnd, yEnd);
            if ((double)sum / area <= t) {
                darkNum++;
            }
        }
    }

    cout << darkNum;
    return 0;
}