颜色与方格 - 题解

标签与难度

标签: 二维滑动窗口, 预处理, 计数, 模拟, 哈希表难度: 1900

题目大意喵~

一位叫小灰灰的朋友有一个 $N \times N$ 的大方格盒子，里面装满了五颜六色的袜子，喵~ 格子 (i, j) 里的袜子颜色是 $c_{i,j}$ 。

小灰灰每次会从一个 $K \times K$ 的小区域里找袜子。我们的任务是，对于 $m$ 次询问，每次给定一个区域的左上角坐标 $(x, y)$ ，我们需要告诉小灰灰，在这个 $K \times K$ 的区域里，有多少种颜色的袜子是至少有两只的（也就是可以凑成一双的啦~）。

简单来说，就是对指定的 $K \times K$ 子矩阵，统计出现次数 $\ge 2$ 的颜色种类数，的说。

解题思路分析

nya~ 看到这道题，我们首先会想到一个最直接的方法！对于每一次询问 $(x, y)$ ，我们就老老实实地遍历这个 $K \times K$ 的区域，用一个哈希表（或者数组）来统计每种颜色的袜子出现了多少次。最后再遍历一遍哈希表，看看有多少种颜色的计数大于等于2，对吧？

这个方法非常直观，但是我们来分析一下它的时间复杂度，喵~ 一个 $K \times K$ 的区域有 $K^2$ 个格子，所以单次查询的时间是 $O(K^2)$ 。总共有 $m$ 次查询，那么总时间复杂度就是 $O(m \cdot K^2)$ 。题目中 $N$ 最大是 700， $K$ 也可能接近 $N$ ， $m$ 也可能很大。如果 $N=700, K=700, m=10^5$ ，那计算量可就太大了，肯定会超时的！我的爪子都要算麻了！必须想个更快的办法，呐。

注意到所有的查询都是在同一个 $N \times N$ 的大网格上进行的。这意味着很多计算是可以复用的！这种“多次查询、固定数据”的模式，通常都在暗示我们使用预处理的技巧。

我们可以预先计算出所有可能的 $K \times K$ 窗口的答案，然后把它们存起来。比如说，用一个二维数组 answers[x][y] 来存储左上角为 $(x, y)$ 的窗口的结果。这样，每次查询只需要 $O(1)$ 的时间去查表就行啦！

那么问题就变成了：如何高效地计算出所有 answers[x][y] 呢？如果对每个可能的 $(x, y)$ 都用 $O(K^2)$ 的方法去算，总时间就是 $O((N-K+1)^2 \cdot K^2) \approx O(N^2 \cdot K^2)$ ，还是太慢了。

这时候，滑动窗口这个聪明的技巧就要登场啦！喵~

想象一下，我们有一个 $K \times K$ 的窗口。当它向右移动一格时，发生了什么变化？窗口最左边的一列被移出去了，同时最右边新的一列被移进来了。中间的大部分区域是保持不变的！

这启发我们可以按行来处理。对于固定的起始行 i，我们先计算出最左边的窗口，也就是以 (i, 1) 为左上角的窗口的答案。然后，我们把这个窗口向右滑动，一列一列地计算出 answers[i][2], answers[i][3], ... 直到 answers[i][N-K+1]。

具体的步骤是这样的，喵~

外层循环：我们从第 1 行开始，一直到第 $N-K+1$ 行，作为我们 $K \times K$ 窗口的起始行 i。
行内初始化：对于每一个起始行 i，我们首先暴力计算第一个窗口，即左上角为 (i, 1) 的窗口的答案。
- 我们用一个 color_counts 数组来统计这个 $K \times K$ 区域内所有颜色的出现次数。
- 同时用一个变量 current_pairs 记录当前能凑成对的颜色种类数。
- 遍历这个 $K \times K$ 的格子，每遇到一个颜色 c，就给 color_counts[c] 加一。如果 color_counts[c] 恰好变成了 2，说明这个颜色刚刚凑成了一对，我们就把 current_pairs 加一。
- 这个初始化步骤的时间复杂度是 $O(K^2)$ 。
行内滑动：计算完第一个窗口后，我们开始向右滑动。当窗口从 (i, j) 移动到 (i, j+1) 时：
- 移除旧列：窗口的最左列，也就是第 j 列，被移除了。我们遍历这一列的 $K$ 个格子。对于每个格子的颜色 c，我们将 color_counts[c] 减一。如果 color_counts[c] 恰好从 2 变成了 1，说明这个颜色刚刚失去了一对，我们就把 current_pairs 减一。
- 添加新列：窗口的最右侧新加入了第 j+K 列。我们遍历这一列的 $K$ 个格子。对于每个格子的颜色 c，我们将 color_counts[c] 加一。如果 color_counts[c] 恰好从 1 变成了 2，说明这个颜色刚刚凑成了一对，我们就把 current_pairs 加一。
- 这样一次滑动的更新操作，只需要处理两列，时间复杂度是 $O(K)$ 。
存储与循环：我们将更新后的 current_pairs 存入 answers[i][j+1]。然后继续向右滑动，直到处理完这一行的所有窗口。
换行处理：处理完一行 i 后，我们移动到下一行 i+1，重复步骤 2-4。在开始处理新的一行之前，需要清空 color_counts 数组和 current_pairs 计数器。

复杂度分析一下这个新方法：

外层循环有 $N-K+1$ 行。
对于每一行，初始化需要 $O(K^2)$ ，之后有 $N-K$ 次滑动，每次滑动需要 $O(K)$ 。所以处理一行的总时间是 $O(K^2 + (N-K) \cdot K) = O(N \cdot K)$ 。
所以，总的预处理时间复杂度是 $O((N-K+1) \cdot N \cdot K) \approx O(N^2 \cdot K)$ 。
预处理完成后，每次查询是 $O(1)$ 。总复杂度为 $O(N^2 \cdot K + m)$ 。

这个复杂度虽然看起来有点高，但在通常的竞赛时间限制下，对于 $N=700$ 这样的数据规模，它是可以通过的！这说明这个方法就是正解啦，喵~

代码实现

下面是我根据上面的思路，精心编写的代码哦！注释写得很详细，希望能帮助你理解，呐~

cpp

#include <iostream>
#include <vector>
#include <numeric> // For std::fill

// 使用快读快写，让程序跑得更快，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}

int main() {
    fast_io();

    int n, m, k;
    std::cin >> n >> m >> k;

    // 读入整个袜子的颜色网格
    // grid[i][j] 表示第 i 行第 j 列的袜子颜色
    // 为了方便处理，我们使用 1-based index，所以数组大小是 (n+1) x (n+1)
    std::vector<std::vector<int>> grid(n + 1, std::vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> grid[i][j];
        }
    }

    // 预处理所有可能的 KxK 窗口的答案
    // answers[i][j] 存储以 (i, j) 为左上角的窗口的结果
    std::vector<std::vector<int>> answers(n + 1, std::vector<int>(n + 1, 0));

    // 用一个大数组来充当颜色计数的哈希表
    // 颜色值最大为 2*10^6，所以数组大小要足够
    std::vector<int> color_counts(2000001, 0);

    // 外层循环：遍历所有可能的窗口起始行 i
    for (int i = 1; i <= n - k + 1; ++i) {
        
        // --- 行内初始化 ---
        // 每换一行，都需要重置计数器
        std::fill(color_counts.begin(), color_counts.end(), 0);
        int current_pairs = 0;

        // 计算本行第一个窗口 (i, 1) 的答案
        for (int r = i; r < i + k; ++r) {
            for (int c = 1; c < 1 + k; ++c) {
                int color = grid[r][c];
                color_counts[color]++;
                // 当一个颜色的数量正好达到2时，我们发现了一个新的可配对颜色
                if (color_counts[color] == 2) {
                    current_pairs++;
                }
            }
        }
        answers[i][1] = current_pairs;

        // --- 行内滑动 ---
        // 从第二个窗口 (i, 2) 开始，通过滑动来计算
        for (int j = 2; j <= n - k + 1; ++j) {
            // 窗口从 (i, j-1) 滑动到 (i, j)
            
            // 1. 移除最左边的列 (j-1)
            for (int r = i; r < i + k; ++r) {
                int color_to_remove = grid[r][j - 1];
                color_counts[color_to_remove]--;
                // 如果移除后，该颜色的数量正好变回1，说明它不再能配对
                if (color_counts[color_to_remove] == 1) {
                    current_pairs--;
                }
            }

            // 2. 添加最右边的新列 (j+k-1)
            for (int r = i; r < i + k; ++r) {
                int color_to_add = grid[r][j + k - 1];
                color_counts[color_to_add]++;
                // 如果添加后，该颜色的数量正好达到2，说明发现了新的可配对颜色
                if (color_counts[color_to_add] == 2) {
                    current_pairs++;
                }
            }
            
            answers[i][j] = current_pairs;
        }
    }

    // 处理 m 次查询
    for (int q = 0; q < m; ++q) {
        int x, y;
        std::cin >> x >> y;
        std::cout << answers[x][y] << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N^2 \cdot K + m)$
- 预处理部分，我们有一个外层循环，迭代了 $N-K+1$ 次（行数）。
- 在每一行内，我们首先花 $O(K^2)$ 的时间初始化第一个窗口。
- 之后进行 $N-K$ 次滑动，每次滑动更新需要 $O(K)$ 的时间。
- 所以处理一行的总时间是 $O(K^2 + (N-K) \cdot K) = O(N \cdot K)$ 。
- 总的预处理时间就是 $(N-K+1) \cdot O(N \cdot K)$ ，约等于 $O(N^2 \cdot K)$ 。
- 查询部分，由于答案已经预处理好了，每次查询只需要 $O(1)$ 的时间，总共是 $O(m)$ 。
- 因此，总时间复杂度为 $O(N^2 \cdot K + m)$ 。
空间复杂度: $O(N^2 + C_{max})$
- 我们需要一个 $O(N^2)$ 的 grid 数组来存储输入。
- 还需要一个 $O(N^2)$ 的 answers 数组来存储预处理的结果。
- color_counts 数组的大小取决于颜色的最大值，记为 $C_{max}$ 。在本题中是 $2 \cdot 10^6$ ，所以空间是 $O(C_{max})$ 。
- 总空间复杂度为 $O(N^2 + C_{max})$ 。

知识点总结

这道题真是一次有趣的冒险，喵~ 我们从中学到了：

滑动窗口算法: 这是解决子数组/子矩阵问题的强大工具。核心思想是复用重叠部分的计算，避免从头开始，从而大大提高效率。
二维问题的降维打击: 我们可以通过固定一个维度（比如行），将一个二维问题转化为多个一维问题来解决。这里我们就是固定了起始行 i，然后在列的方向上进行一维滑动。
预处理思想: 当面临大量查询且数据本身不变时，预处理所有可能的结果是一种非常有效的策略。用空间换时间，喵~
计数技巧: 使用数组作为哈希表来计数是非常高效的。关键在于如何根据计数值的变化来维护最终答案（比如本题中的 current_pairs）。只在计数值跨过关键阈值（这里是2）时才更新答案，而不是每次都重新统计。

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问我，喵~ >w<

颜色与方格 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​