H2. Maximize the Largest Component (Hard Version) - 题解

比赛与标签

比赛: Codeforces Round 952 (Div. 4) 标签: data structures, dfs and similar, dp, dsu, implementation 难度: *2200

任务简报喵~ 题目到底要我们做什么？

喵~ 各位算法大师们好呀！我是你们最爱解题的小猫娘，今天我们来攻克一道非常有趣的网格题，准备好了吗？让我们一起看看怎么才能拼出最大的连通块吧！

这道题是这样子的：我们有一个 n x m 大小的网格，里面有些格子是 . (空地)，有些是 # (墙壁)，的说。一个连通的 # 区域，我们称之为一个“连通块”，它的大小就是其中 # 格子的数量。

我们被赋予了一次超能力！最多只能用一次哦！这个能力是：选择任意一行 r 和任意一列 c，然后把这一整行和这一整列的所有格子都变成 #。这就像在网格上画了一个大大的十字！

我们的任务就是，合理地使用这次（或者不用）超能力，使得操作之后，网格中最大的那个 # 连通块的尺寸达到最大！然后把这个最大尺寸告诉我就好啦，喵~

解题思路大揭秘！The Meow-ster Plan!

直接枚举我们要在哪一行哪一列施展“十字魔法”，然后每次都用DFS或BFS去计算最大连通块的大小，那可太慢啦，会超时的说！(n*m个选择，每次计算又耗费n*m，总共O((nm)^2)，不行不行！)。我们得像猫咪一样，用更聪明、更敏捷的方法出击！

整个解题思路可以分成三步走，喵~

第一步：摸清现状，用DSU找到初始的小伙伴们

在施展魔法之前，我们得先了解一下地图上已有的 # 格局，对吧？这些 # 可能已经自己形成了一些连通块，就像一个个孤立的小岛。

这时候，并查集 (Disjoint Set Union, DSU) 就闪亮登场啦！它简直是寻找和合并连通块的神器，又快又好用。

我们把 n*m 的网格看成 n*m 个独立的点。
遍历整个网格，当遇到一个 # 格子 (i, j) 时，我们就看看它的右边 (i, j+1) 和下边 (i+1, j) 是不是也是 #。如果是，就用并查集的 unite 操作把它们合并到同一个集合里。
遍历完后，DSU 就帮我们把所有的初始连通块都找出来啦！我们可以轻松得到每个连通块的根节点、以及它的大小（集合里元素的数量）。

第二步：分析“十字魔法”的威力

当我们选择在 (r, c) 处施法，会发生什么呢？新生成的这个十字会把所有它“碰到”的初始连通块，以及十字本身，全部连接成一个巨大的新连通块！

一个初始连通块 k 会被“碰到”，只要十字的行 r 或者列 c 与 k 的边界相邻。为了方便判断，我们可以预先计算出每个连通块 k 的包围盒 (Bounding Box)，也就是它所占据的最小行号 min_r、最大行号 max_r、最小列号 min_c 和最大列号 max_c。

如果 r 在 [min_r - 1, max_r + 1] 范围内，行 r 就碰到了它。
如果 c 在 [min_c - 1, max_c + 1] 范围内，列 c 就碰到了它。

那么，选择 (r, c) 后新形成的大连通块的总大小可以这样计算： 总大小 = (十字本身的大小) + (所有被连接的初始连通块的大小之和) - (重叠部分的大小)

十字本身的大小: n + m - 1。
被连接的初始连通块: 设 S_r 是被行 r 碰到的连通块集合，S_c 是被列 c 碰到的连通块集合。那么所有被连接的块就是 S_r ∪ S_c。它们的大小之和是 SumSize(S_r) + SumSize(S_c) - SumSize(S_r ∩ S_c)。
重叠部分: 十字经过的格子里，原本就是 # 的那些。这等于 (第 r 行的'#'数) + (第 c 列的'#'数) - (如果(r,c)是'#'则为1，否则为0)。

把这些合在一起，对于给定的 (r, c)，最终大小的增量部分（相对于十字本身）可以表示为： Extra(r, c) = SumSize(S_r) + SumSize(S_c) - SumSize(S_r ∩ S_c) - (num_hash_row[r] + num_hash_col[c] - is_hash(r,c))

我们的目标就是找到使 Extra(r, c) 最大的 (r, c)。

第三步：终极优化！扫描线 + 差分数组

暴力枚举 r 和 c 还是太慢。我们可以固定一行 r，然后尝试快速地找出与它搭配的最优列 c。

当我们固定了 r，上面公式中的 SumSize(S_r) 和 num_hash_row[r] 就都变成常数啦。我们需要优化的部分是关于 c 的： Maximize_c [ SumSize(S_c) - SumSize(S_r ∩ S_c) - num_hash_col[c] + is_hash(r,c) ]

这里最麻烦的就是 SumSize(S_r ∩ S_c) 这一项，它同时依赖 r 和 c。但是！对于固定的 r，一个连通块 k 是否属于 S_r 是确定的。如果 k 属于 S_r，那么当 c 落在 k 的列包围盒附近时 ([min_c-1, max_c+1])，k 就会对 SumSize(S_r ∩ S_c) 产生贡献。

这是一个典型的区间更新问题！对于每个属于 S_r 的连通块 k，我们需要给某一列范围 [l, ri] 内的所有 c 的计算值都减去 size(k)。

这时候，差分数组 (Difference Array) 就派上用场了！

我们创建一个差分数组 delta。
对于固定的 r，遍历所有与它相邻的连通块 k (也就是 S_r 里的块)。
对于每个这样的 k，在差分数组 delta 的 l = max(0, min_c-1) 位置减去 size(k)，在 ri+1 = min(m-1, max_c+1)+1 的位置加上 size(k)。
处理完所有与 r 相邻的块后，我们从左到右扫描所有列 c。通过计算 delta 数组的前缀和，我们就能在 O(1) 的时间内得到每个 c 对应的 SumSize(S_r ∩ S_c) 的值！

这样，对于每一行 r，我们都可以在 O(m + |S_r|) 的时间内找到最优的 c。总的时间复杂度就优化到了 O(n*m) 级别，完美通过！喵~

最后别忘了，我们还可以选择不操作。所以最终答案是 max(初始最大连通块大小, 十字魔法能创造的最大连通块大小)。

代码实现喵！Let's Get Our Paws Dirty!

cpp

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <map>
#include <tuple>

using namespace std;

// DSU (并查集) 数据结构，用来寻找和合并连通块，喵~
struct DSU {
    vector<int> parent;
    vector<int> sz; // 记录每个集合的大小
    DSU(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0); // 初始化，每个元素自成一派
        sz.assign(n, 1);
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); // 路径压缩，让查找更快！
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j); // 按大小合并，优化树高
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
        }
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // --- 步骤 1: 使用 DSU 找到初始的连通块 ---
    DSU dsu(n * m);
    bool has_hash = false; // 记录网格里是否有 '#'
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '#') {
                has_hash = true;
                // 和下面的 '#' 合并
                if (i + 1 < n && grid[i + 1][j] == '#') {
                    dsu.unite(i * m + j, (i + 1) * m + j);
                }
                // 和右边的 '#' 合并
                if (j + 1 < m && grid[i][j + 1] == '#') {
                    dsu.unite(i * m + j, i * m + j + 1);
                }
            }
        }
    }

    // 特殊情况：如果一个 '#' 都没有，那我们画个十字就是 n+m-1 大小
    if (!has_hash) {
        cout << n + m - 1 << endl;
        return;
    }

    // --- 对连通块进行重新编号和信息统计 ---
    map<int, int> root_to_comp_idx;
    int component_count = 0;
    // 把 DSU 的 root 映射到 0, 1, 2... 这样的连续编号，方便后续处理
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '#') {
                int root = dsu.find(i * m + j);
                if (root_to_comp_idx.find(root) == root_to_comp_idx.end()) {
                    root_to_comp_idx[root] = component_count++;
                }
            }
        }
    }

    vector<long long> final_comp_size(component_count); // 存储每个连通块的大小
    vector<int> comp_id(n * m, -1); // 存储每个 '#' 格子属于哪个连通块
    for (auto const& [root, idx] : root_to_comp_idx) {
        final_comp_size[idx] = dsu.sz[root];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '#') {
                comp_id[i * m + j] = root_to_comp_idx[dsu.find(i * m + j)];
            }
        }
    }

    // 计算每个连通块的包围盒 (Bounding Box)，这是优化的关键！
    vector<tuple<int, int, int, int>> comp_bbox(component_count, {n, -1, m, -1}); // {min_r, max_r, min_c, max_c}
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '#') {
                int id = comp_id[i * m + j];
                get<0>(comp_bbox[id]) = min(get<0>(comp_bbox[id]), i);
                get<1>(comp_bbox[id]) = max(get<1>(comp_bbox[id]), i);
                get<2>(comp_bbox[id]) = min(get<2>(comp_bbox[id]), j);
                get<3>(comp_bbox[id]) = max(get<3>(comp_bbox[id]), j);
            }
        }
    }

    // --- 步骤 2: 预计算 ---
    vector<int> num_hash_row(n, 0), num_hash_col(m, 0); // 每行每列的 '#' 数量
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '#') {
                num_hash_row[i]++;
                num_hash_col[j]++;
            }
        }
    }

    // 预计算每行/每列能连接到的连通块的总大小
    vector<long long> row_potential(n, 0);
    vector<long long> col_potential(m, 0);
    vector<vector<int>> comps_by_row_proximity(n); // 记录每行能碰到的连通块ID

    for (int k = 0; k < component_count; ++k) {
        auto [min_r, max_r, min_c, max_c] = comp_bbox[k];
        // 如果行 r 在包围盒上下扩展一格的范围内，它就能连接到这个块
        for (int r = max(0, min_r - 1); r <= min(n - 1, max_r + 1); ++r) {
            row_potential[r] += final_comp_size[k];
            comps_by_row_proximity[r].push_back(k);
        }
        // 如果列 c 在包围盒左右扩展一格的范围内...
        for (int c = max(0, min_c - 1); c <= min(m - 1, max_c + 1); ++c) {
            col_potential[c] += final_comp_size[k];
        }
    }

    // --- 步骤 3: 主计算，使用扫描线思想 ---
    long long max_extra_val = -4e18; // 记录最大的额外收益，初始化为一个很小的值

    // 遍历每一行 r 作为我们施法的地方
    for (int r = 0; r < n; ++r) {
        long long row_base_val = row_potential[r] - num_hash_row[r];
        
        vector<long long> col_vals(m);
        for (int c = 0; c < m; ++c) {
            col_vals[c] = col_potential[c] - num_hash_col[c] + (grid[r][c] == '#');
        }

        // 使用差分数组来计算 SumSize(S_r ∩ S_c)
        vector<long long> delta(m + 2, 0);
        for (int k : comps_by_row_proximity[r]) {
            auto [min_r, max_r, min_c, max_c] = comp_bbox[k];
            int l = max(0, min_c - 1);
            int ri = min(m - 1, max_c + 1);
            if (l <= ri) {
                // 对于列范围 [l, ri]，它们都会和块 k 同时接触，所以要减去 k 的大小
                delta[l] -= final_comp_size[k];
                delta[ri + 1] += final_comp_size[k];
            }
        }

        long long current_delta = 0;
        // 扫描所有列 c
        for (int c = 0; c < m; ++c) {
            current_delta += delta[c]; // 累加差分值，得到当前列 c 的修正项
            long long current_extra_val = row_base_val + col_vals[c] + current_delta;
            max_extra_val = max(max_extra_val, current_extra_val);
        }
    }

    // --- 最终答案 ---
    long long ans = 0;
    // 首先，答案至少是初始时最大的连通块大小（不操作的情况）
    if (component_count > 0) {
        ans = *max_element(final_comp_size.begin(), final_comp_size.end());
    }
    
    // 然后和操作后的最优结果比较
    // 最终大小 = 十字大小 + 额外收益
    ans = max(ans, (long long)n + m - 1 + max_extra_val);
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析 (How Fast is Our Pounce?)

时间复杂度: O(N*M) 的说。
- DSU 初始化和合并的过程接近线性，为 O(N*M * α(N*M))，其中 α 是阿克曼函数的反函数，基本可以看作是常数。
- 预计算包围盒、potential数组等，总的计算量和所有连通块的周长之和有关，但总和不会超过 O(N*M)。
- 主循环遍历 n 行，每行内部的扫描线部分，包括构建差分数组和扫描列，总的计算量分摊下来也是 O(N*M)。所以整体是线性的，非常快！
空间复杂度: O(N*M) 的说。
- 我们需要存储整个网格、DSU的 parent 和 sz 数组、以及 comp_id 等，这些都需要 O(N*M) 的空间。

知识点与总结 (What We've Learned, Meow!)

这道题真是对思维和代码实现能力的一次大考验呢！不过只要我们一步步拆解问题，找到关键的优化点，就没有什么能难倒我们的喵~

DSU (并查集): 寻找网格连通块的经典利器！是图论问题中的常客，一定要熟练掌握呐。
预计算与空间换时间: 通过预先计算好每个连通块的包围盒、大小，以及每行每列的 # 数量，避免了在主循环中重复计算，是优化的基础。
扫描线与差分数组: 这是本题从暴力解法迈向高效解法的核心！当遇到一个二维问题，需要固定一个维度，优化另一个维度上的区间计算时，扫描线+差分（或线段树等）是非常强大的思想工具。
问题分解: 将复杂的总大小计算公式，分解成与 r 相关、与 c 相关、与 (r,c) 共同相关的几个部分，是看清问题结构、找到优化方向的关键一步。

希望这篇题解能帮到你，让你感受到算法的魅力！下次再一起挑战更有趣的题目吧！喵~

H2. Maximize the Largest Component (Hard Version) - 题解 ​

比赛与标签 ​

任务简报喵~ 题目到底要我们做什么？ ​

解题思路大揭秘！The Meow-ster Plan! ​

第一步：摸清现状，用DSU找到初始的小伙伴们 ​

第二步：分析“十字魔法”的威力 ​

第三步：终极优化！扫描线 + 差分数组 ​

代码实现喵！Let's Get Our Paws Dirty! ​

复杂度分析 (How Fast is Our Pounce?) ​

知识点与总结 (What We've Learned, Meow!) ​