F. Goblin - 题解

比赛与标签

比赛: Codeforces Round 1020 (Div. 3) 标签: dfs and similar, dp, dsu, greedy, math 难度: *1900

题目大意喵~

你好呀，未来的算法大师！这道题是说，有一个聪明的地精要解决一个谜题，我们来帮帮他吧，喵~

首先，我们有一个长度为 n 的二进制字符串 s。然后，我们根据 s 生成 n 个新的字符串 a_1, a_2, ..., a_n。其中，a_i 是把 s 的第 i 个字符翻转（'0' 变 '1'，'1' 变 '0'）得到的。

接着，用这些 a_i 组成一个 n x n 的网格 g，其中第 i 行就是字符串 a_i。

我们的任务是，在这个网格 g 中找到一个由 '0' 组成的、连通的区域，并计算出这个区域包含的 '0' 的最大数量。所谓的“连通”，就是指从这个区域里的任意一个 '0' 出发，只走上下左右相邻的 '0'，可以到达区域里所有其他的 '0'。

简单来说，就是要找网格中最大的 '0' 连通块的大小，的说！

解题思路喵！

直接构建一个 n x n 的网格是行不通的，因为 n 太大了，会超时和超内存的呐。所以，我们必须找到一种更聪明的方法，不需要真正把网格画出来，喵~

让我们先分析一下网格 g 中 g[i][j] (第 i 行, 第 j 列) 的值是怎么来的：

• a_i 是 s 翻转第 i 个字符得到的。
• 所以，a_i 的第 j 个字符 a_i[j]，就是 g[i][j]。
• 如果 i == j（在主对角线上），g[i][i] 的值就是 s[i] 翻转后的结果。
• 如果 i != j（不在主对角线上），g[i][j] 的值就和 s[j] 相同。

那么，g[i][j] 什么时候是 '0' 呢？

1. 当 i != j 时，如果 s[j] == '0'，那么 g[i][j] 就是 '0'。
2. 当 i == j 时，如果 s[j] == '1'，那么 g[j][j] 就是 '0'。

这个结构给了我们一个重要的提示：网格中 '0' 的分布完全由原始字符串 s 决定！

核心思路：并查集 (DSU) + 抽象建模

我们可以把连通的 '0' 看作一个集合。寻找最大连通块，自然就想到了并查集（Disjoint Set Union, DSU）啦！我们可以把每个 '0' 看作一个点，然后把相邻的 '0' 合并到同一个集合里。但是 n*n 个点还是太多了，所以我们要把 '0' 分组来处理。

Step 1: 发现 '0' 的大部队

观察一下，如果 s 中有一段连续的 '0'，比如从下标 p 开始，长度为 k 的一段 00...0，会发生什么呢？ 对于这一段中的任意一列 j (p <= j < p+k)，因为 s[j] == '0'，所以这一整列除了对角线上的 g[j][j] 之外，全都是 '0'！ 这 k 个几乎全为 '0' 的列，以及它们之间通过行的连接，会形成巨大无比的 '0' 连通块！

Step 2: 拆分连通块

对于这样一个由 s 中连续 k 个 '0'（从 p 开始）形成的 '0' 的区域，它并不是完全连通的。因为它被主对角线上的 '1'（因为 s[j]=='0', 所以 g[j][j]=='1'）给分开了。 仔细分析可以发现，这个区域被分成了两个主要的连通部分：

1. “上半部分”：由第 0 到 p-1 行的 '0'，以及第 p 到 p+k-1 行中，在主对角线下方的 '0' 组成。
   • 第 0 到 p-1 行，在 p 到 p+k-1 列的区域，有 p * k 个 '0'。
   • 在第 p 到 p+k-1 行和列构成的 k x k 方块中，主对角线下方的 '0' 有 k*(k-1)/2 个。
   • 总大小为 p * k + k * (k-1) / 2。
2. “下半部分”：由第 p+k 到 n-1 行的 '0'，以及第 p 到 p+k-1 行中，在主对角线上方的 '0' 组成。
   • 第 p+k 到 n-1 行，在 p 到 p+k-1 列的区域，有 (n - (p+k)) * k 个 '0'。
   • 在 k x k 方块中，主对角线上方的 '0' 也有 k*(k-1)/2 个。
   • 总大小为 (n - (p+k)) * k + k * (k-1) / 2。

所以，s 中的每一段连续的 '0'，我们都可以在并查集中创建两个节点，分别代表这两个连通块，并记录下它们的大小。

Step 3: 寻找“桥梁”

现在，不同的 '0' 块之间是独立的。是什么能把它们连接起来呢？是 s 中的 '1'！ 当 s[j] == '1' 时，对角线上的 g[j][j] 就是 '0'。这个 '0' 就像一座桥梁，可以连接它左右两侧的 '0'。

• g[j][j-1] 的值是 s[j-1]。
• g[j][j+1] 的值是 s[j+1]。

所以，如果 s[j-1] 和 s[j+1] 都是 '0'，那么 g[j][j-1] 和 g[j][j+1] 也都是 '0'。这样，g[j][j] 这个 '0' 就把它们连接起来了！

• g[j][j-1] 这个 '0' 属于它左边那个 '0' 块的“下半部分”。
• g[j][j+1] 这个 '0' 属于它右边那个 '0' 块的“上半部分”。

于是，一个 ...010... 结构，就会把左边 '0' 块的“下半部分”和右边 '0' 块的“上半部分”合并起来。合并后的新连通块大小就是两个旧块大小之和，再加上桥梁 g[j][j] 本身的 1。

其他情况：

• 如果是 ...011... 结构，g[j][j] 只连接了左边的 '0' 块，那就只给左边 '0' 块的“下半部分”大小加 1。
• 如果是 ...110... 结构，g[j][j] 只连接了右边的 '0' 块，那就只给右边 '0' 块的“上半部分”大小加 1。
• 如果是 ...111... 结构，g[j][j] 是一个孤立的 '0'，它自己形成一个大小为 1 的连通块。

总结一下我们的算法：

1. 遍历字符串 s，找出所有连续的 '0' 块。
2. 为每个 '0' 块，在并查集中创建两个节点，计算出“上半部分”和“下半部分”的大小。
3. 遍历字符串 s 中的所有 '1'。根据 '1' 的邻居是 '0' 还是 '1'，来合并或增大对应 '0' 块的连通分量。
4. 在整个过程中，不断更新我们见过的最大连通块的大小。
5. 最后，别忘了考虑 s 全是 '1' 的情况（答案是1），以及被 '1' 包围的孤立 '0'（也是大小为1的块）。最终答案就是所有可能中的最大值。

这样，我们就能在 O(n) 的时间内解决问题啦，是不是很巧妙呢，喵~

代码实现

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

// DSU (并查集) 结构体，用来管理连通块的合并和查询，喵~
struct DSU {
    std::vector<int> parent;    // 存储每个节点的父节点
    std::vector<long long> sz;  // 存储每个根节点代表的集合大小

    DSU(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0); // 初始化，每个节点都是自己的父节点
        sz.assign(n, 0); // 初始化大小为0
    }

    // 查找节点i所属集合的根节点
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]); // 路径压缩优化
    }

    // 合并i和j所在的集合，extra_size是桥梁'0'的大小（通常是1）
    void unite(int i, int j, long long extra_size) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // 按大小合并，小集合并入大集合，可以优化性能
            if (sz[root_i] < sz[root_j]) std::swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j] + extra_size; // 新集合大小 = 两集合大小 + 桥梁大小
        } else {
            // 如果已经在同一个集合，说明这个'0'只是给这个集合增加了一个节点
            sz[root_i] += extra_size;
        }
    }
};

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // Step 1: 找到 s 中所有连续的 '0' 块
    std::vector<std::pair<int, int>> zero_blocks; // 存储每个'0'块的 {起始位置, 长度}
    std::map<int, int> idx_to_block_id;           // 建立'0'字符的下标到它所属块ID的映射

    int i = 0;
    while (i < n) {
        if (s[i] == '0') {
            int j = i;
            while (j < n && s[j] == '0') {
                j++;
            }
            int start = i;
            int len = j - i;
            zero_blocks.push_back({start, len});
            int block_id = zero_blocks.size() - 1;
            for (int k = start; k < j; ++k) {
                idx_to_block_id[k] = block_id;
            }
            i = j;
        } else {
            i++;
        }
    }

    // 特殊情况：如果s中没有'0'，全是'1'，那么对角线上会有一排孤立的'0'，最大连通块大小为1
    if (zero_blocks.empty()) {
        std::cout << 1 << "\n";
        return;
    }

    // Step 2: 初始化并查集。每个'0'块产生两个初始连通分量
    int num_dsu_nodes = 2 * zero_blocks.size();
    DSU dsu(num_dsu_nodes);
    long long max_sz = 0;

    for (size_t b_id = 0; b_id < zero_blocks.size(); ++b_id) {
        long long p = zero_blocks[b_id].first;
        long long k = zero_blocks[b_id].second;
        
        // 分量A: '0'块“上半部分”的大小
        long long comp_a_size = p * k + k * (k - 1) / 2;
        // 分量B: '0'块“下半部分”的大小
        long long comp_b_size = (long long)(n - (p + k)) * k + k * (k - 1) / 2;

        dsu.sz[2 * b_id] = comp_a_size;       // 节点 2*b_id 代表分量A
        dsu.sz[2 * b_id + 1] = comp_b_size; // 节点 2*b_id+1 代表分量B
        
        max_sz = std::max({max_sz, comp_a_size, comp_b_size});
    }

    // Step 3: 处理s中的'1'，它们是连接不同分量的“桥梁”
    long long isolated_ones_max = 0; // 记录孤立'1'产生的'0'连通块大小（最大为1）
    for (int j = 0; j < n; ++j) {
        if (s[j] == '1') {
            bool left_is_0 = (j > 0 && s[j - 1] == '0');
            bool right_is_0 = (j < n - 1 && s[j + 1] == '0');

            if (left_is_0 && right_is_0) {
                // '1' 在两个 '0' 块之间，充当桥梁
                int block_L_id = idx_to_block_id[j - 1];
                int block_R_id = idx_to_block_id[j + 1];
                int u = 2 * block_L_id + 1; // 左边'0'块的“下半部分”
                int v = 2 * block_R_id;     // 右边'0'块的“上半部分”
                dsu.unite(u, v, 1); // 合并，并加上桥梁本身的大小1
                max_sz = std::max(max_sz, dsu.sz[dsu.find(u)]);
            } else if (left_is_0) {
                // '1' 只连接了左边的 '0' 块
                int block_L_id = idx_to_block_id[j - 1];
                int u = 2 * block_L_id + 1;
                int root_u = dsu.find(u);
                dsu.sz[root_u]++; // 对应连通块大小+1
                max_sz = std::max(max_sz, dsu.sz[root_u]);
            } else if (right_is_0) {
                // '1' 只连接了右边的 '0' 块
                int block_R_id = idx_to_block_id[j + 1];
                int v = 2 * block_R_id;
                int root_v = dsu.find(v);
                dsu.sz[root_v]++; // 对应连通块大小+1
                max_sz = std::max(max_sz, dsu.sz[root_v]);
            } else {
                // '1' 被 '1' 包围或在边界，形成一个孤立的'0'，大小为1
                isolated_ones_max = 1;
            }
        }
    }
    
    // 最终答案是所有情况中的最大值
    std::cout << std::max(max_sz, isolated_ones_max) << "\n";
}

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

复杂度分析

• 时间复杂度: O(N) 的说，其中 N 是所有测试用例的 n 的总和。

  • 我们遍历字符串 s 来找 '0' 块，这是 O(n) 的。
  • 初始化并查集和计算初始大小是 O(number of blocks)，最多是 O(n)。
  • 遍历 s 中的 '1' 来合并连通块也是 O(n) 的。
  • 并查集的操作（find 和 unite）加上路径压缩和按大小合并优化后，平均时间复杂度接近 O(α(n))，可以看作是常数时间。
  • 所以总的来说，每个测试用例都是线性的，非常高效！

• 空间复杂度: O(N) 的说，同样 N 是所有 n 的总和。

  • zero_blocks 向量和 idx_to_block_id map 在最坏情况下可能需要 O(n) 的空间。
  • 并查集的 parent 和 sz 数组的大小与 '0' 块的数量成正比，也是 O(n) 级别的。

知识点与总结

这道题真是一次有趣的冒险，不是吗？它教会了我们几件重要的事情呐：

1. 抽象建模: 面对看似庞大复杂的问题（比如 n x n 的网格），不要害怕！关键是分析其内在结构和规律，把它转化成我们熟悉的、更简单的模型。这道题就是把网格连通性问题，变成了基于一维字符串 s 的分块和合并问题。
2. 并查集 (DSU) 的妙用: DSU 是处理动态连通性问题的神器！当你需要管理一堆元素，不断地把它们合并到不同的集合中，并查询它们是否连通或集合大小时，第一时间就应该想到它，喵~
3. 分而治之: 我们把问题分解成了几个部分：处理'0'块，处理'1'桥梁，再把它们组合起来。这种把大问题拆解成小问题的思想，是算法解题中的核心策略之一。

希望这次的解说能帮助你更好地理解这道题！解题就像寻宝一样，只要有耐心和智慧，总能找到藏在代码深处的宝藏。继续加油哦，你一定可以成为最厉害的算法大师的！喵~ ✨