E. Connected Component on a Chessboard - 题解

比赛与标签

比赛: Codeforces Round 575 (Div. 3) 标签: constructive algorithms, implementation 难度: *1800

喵喵，我们接到了一个新任务！(题目大意)

主人，你好呀~！这次的任务是在一个无限大的棋盘上玩拼图游戏，喵~！

棋盘的 (1,1) 位置是白色的，然后黑白格子交替。一个格子的颜色由它的坐标 (r, c) 决定：如果 r+c 是偶数，它就是白色；如果是奇数，它就是黑色，很简单对吧？

我们需要根据给定的两种颜色的格子数量——b 个黑色格子和 w 个白色格子——在棋盘上找出这样一块区域，它要满足：

1. 正好包含 b 个黑色格子和 w 个白色格子。
2. 所有这些格子必须形成一个连通块。也就是说，从这个区域里的任何一个格子出发，都可以只经过区域内的其他格子，走到任何另外一个格子。两个格子相邻就算连接哦（上、下、左、右）。

如果能找到这样的区域，就输出 "YES"，然后把所有格子的坐标打印出来。如果找不到，就告诉人家 "NO" 就好啦。我们要处理好多好多个这样的询问呢，加油喵！

本猫娘的绝妙计划！(解题思路)

这是一个构造题，意思就是我们不需要去搜索，而是直接想办法“造”出一个符合条件的答案！这种题目最考验我们的创造力了，喵~

什么时候会失败呢？

首先，我们来想想看，在什么情况下会构造失败。关键在于“连通”这个条件。为了让所有格子连在一起，它们必须相互接触。

一个颜色的格子，它的所有邻居都是另一种颜色。比如说，一个黑格子，它的上、下、左、右四个邻居都是白格子。

让我们来思考一下，用数量少的那种颜色的格子，去“粘合”数量多的那种颜色的格子。假设白格子 w 比黑格子 b 多（w >= b）。 我们用 b 个黑格子作为“骨架”或者“胶水”，把 w 个白格子粘起来。

一个黑格子最多能连接几个白格子呢？答案是4个！ 那么 b 个黑格子最多能连接 4*b 个白格子吗？不完全是哦，因为黑格子自己之间也可能需要通过白格子来连接，这会消耗掉一些连接白格子的“接口”。

我们来想一种最“节省”黑格子的构造方式，看看 b 个黑格子最多能撑起多少个白格子。 我们可以这样：

1. 先用 b 个黑格子和 b+1 个白格子组成一条长长的、颜色交错的“脊椎”，像这样：W-B-W-B-...-W。这条脊椎本身就是连通的，并且已经包含了 b 个黑格子和 b+1 个白格子。
2. 现在，这条脊椎上的每一个黑格子，它的上下两个位置都还是空着的。这些位置的格子一定是白色的！因为行坐标变化了1，r+c 的奇偶性就变了。
3. 我们有 b 个黑格子，每个黑格子都能提供上下两个新的位置来放白格子。所以，我们额外有 2*b 个位置可以放白格子。

综上所述，用 b 个黑格子，我们最多可以构造出一个包含 b+1 (脊椎上的) + 2*b (脊椎外的) = 3*b + 1 个白格子的连通块。

所以，如果需要的白格子数量 w 超过了 3*b + 1，那无论怎么摆，b 个黑格子都“粘”不起来这么多白格子啦，任务就失败了！

同理，如果黑格子比白格子多（b > w），那么 w 个白格子最多也只能连接 3*w + 1 个黑格子。如果 b > 3*w + 1，任务同样会失败。

所以，我们的无解条件就是：w > 3 * b + 1 或者 b > 3 * w + 1。只要不满足这个条件，我们总能构造出解！

怎么构造一个“YES”的答案呢？

既然知道了什么时候有解，那我们就来动手构造吧！我们分两种情况讨论，这两种情况是对称的。

情况一：白格子比较多或者一样多 (w >= b)

1. 打好基础: 我们先在棋盘上找个地方，比如以 (200002, 200002) 这个白格子为起点（选个大坐标是为了防止算着算着跑到负数去，是个好习惯哦！）。我们先铺设一条 2*b + 1 个格子的长条作为“脊椎”： (R, C), (R, C+1), ..., (R, C+2b) 因为 R+C 是偶数，所以这条线的颜色是 W, B, W, B, ..., W。 这样一来，我们已经用掉了 b 个黑格子和 b+1 个白格子，并且它们是连通的。

2. 添砖加瓦: 现在我们还差 w - (b+1) 个白格子。还记得吗？脊椎上的每个黑格子 (R, C+2k+1) 的上下邻居 (R-1, C+2k+1) 和 (R+1, C+2k+1) 都是白格子，而且还没被使用。 我们只需要从第一个黑格子开始，依次给它们“挂上”上下的白格子，直到我们需要的 w 个白格子全部用完为止。因为我们已经排除了 w > 3b+1 的情况，所以 w - (b+1) <= 2b，这意味着我们拥有的 2b 个空位是绝对足够的！

情况二：黑格子比较多 (b > w)

这种情况和上面完全对称，喵~

1. 打好基础: 我们需要让“脊椎”以黑格子开头。很简单，把起点行坐标加一就行了。我们以 (200003, 200002) 这个黑格子为起点，铺设一条 2*w + 1 个格子的长条： (R+1, C), (R+1, C+1), ..., (R+1, C+2w) 这条线的颜色就是 B, W, B, W, ..., B。 这样我们就用掉了 w 个白格子和 w+1 个黑格子。

2. 添砖加瓦: 现在我们还差 b - (w+1) 个黑格子。脊椎上的每个白格子 (R+1, C+2k+1) 的上下邻居 (R, C+2k+1) 和 (R+2, C+2k+1) 都是黑格子。我们同样把剩下的黑格子挂上去就好啦！

这样，无论哪种情况，我们都能完美地构造出符合要求的连通块，任务完成，可以去要小鱼干了，喵呜~！

让代码动起来！(代码实现)

#include <iostream>
#include <vector>
#include <algorithm>

void solve() {
    long long b, w;
    std::cin >> b >> w;

    // 根据我们推导出的极限条件，判断是否无解
    // 一个颜色作为“胶水”，最多能粘合的另一种颜色的数量是 3*N+1
    if (w > 3 * b + 1 || b > 3 * w + 1) {
        std::cout << "NO\n";
        return;
    }

    std::cout << "YES\n";
    // 选一个足够大的基准坐标，防止后续计算出现负数或0
    long long base_r = 200002;
    long long base_c = 200002;

    // 情况一：白格子数量不小于黑格子
    if (w >= b) {
        // 我们需要 w 个白格子, b 个黑格子
        // 核心思路是先构造一个包含 b 个黑格子和 b+1 或 b 个白格子的“脊椎”
        
        // 如果 w == b，构造一个 2b 长度的脊椎 W,B,W,B...
        // 这会正好给出 b 个白格子和 b 个黑格子
        if (w == b) {
            for (int i = 0; i < 2 * b; ++i) {
                // (base_r, base_c) 是白色, (base_r, base_c+1) 是黑色, 交替进行
                std::cout << base_r << " " << base_c + i << "\n";
            }
            return;
        }

        // 如果 w > b，构造一个 2b+1 长度的脊椎 W,B,W,B,...,W
        // 这会给出 b+1 个白格子和 b 个黑格子
        for (int i = 0; i <= 2 * b; ++i) {
            std::cout << base_r << " " << base_c + i << "\n";
        }

        // 现在我们有了 b 个黑格子和 b+1 个白格子，还需要 w - (b+1) 个白格子
        long long rem_w = w - (b + 1);

        // 我们把剩下的白格子加到脊椎上黑格子的旁边
        // 脊椎上的黑格子坐标为 (base_r, base_c + 1), (base_r, base_c + 3), ...
        for (int k = 0; k < b && rem_w > 0; ++k) {
            long long black_c = base_c + 2 * k + 1;
            // 在黑格子的上方添加一个白格子
            std::cout << base_r - 1 << " " << black_c << "\n";
            rem_w--;
            if (rem_w > 0) {
                // 如果还需要，就在下方也添加一个白格子
                std::cout << base_r + 1 << " " << black_c << "\n";
                rem_w--;
            }
        }
    } else { // b > w
        // 情况二：黑格子数量大于白格子，逻辑完全对称
        
        // 我们需要 b 个黑格子, w 个白格子
        // 同样构造脊椎，但这次要以黑格子开头
        // 我们把基准行+1，(base_r+1, base_c) 的坐标和为奇数，是黑格子
        
        // 构造一个 2w+1 长度的脊椎 B,W,B,W,...,B
        // 这会给出 w+1 个黑格子和 w 个白格子
        for (int i = 0; i <= 2 * w; ++i) {
            std::cout << base_r + 1 << " " << base_c + i << "\n";
        }

        // 现在我们有了 w 个白格子和 w+1 个黑格子，还需要 b - (w+1) 个黑格子
        long long rem_b = b - (w + 1);

        // 把剩下的黑格子加到脊椎上白格子的旁边
        // 脊椎上的白格子坐标为 (base_r+1, base_c + 1), (base_r+1, base_c + 3), ...
        for (int k = 0; k < w && rem_b > 0; ++k) {
            long long white_c = base_c + 2 * k + 1;
            // 在白格子的上方添加一个黑格子
            std::cout << base_r << " " << white_c << "\n";
            rem_b--;
            if (rem_b > 0) {
                // 如果还需要，就在下方也添加一个黑格子
                std::cout << base_r + 2 << " " << white_c << "\n";
                rem_b--;
            }
        }
    }
}

int main() {
    // 优化输入输出，让程序跑得更快，像小猫一样敏捷~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int q;
    std::cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}

小猫跑得快不快？(复杂度分析)

• 时间复杂度: O(∑(b+w)) 的说。 对于每一个询问，我们都需要输出 b+w 个坐标。因为题目保证了所有询问的 b+w 总和不超过一个定值（比如 2*10^5），所以总的时间复杂度和这个总和是成正比的。我们的构造方法没有复杂的循环，只是简单地打印坐标，所以效率非常高！

• 空间复杂度: O(1) 的说。 在处理每个询问时，我们没有使用额外的数组或者容器来存储大量的坐标。我们是边计算边输出的，所以只需要几个变量来存储 b, w 和基准坐标等信息。占用的内存是恒定的，非常节省空间，喵~

本次探险的收获！(知识点与总结)

这次任务真是太有趣啦！我们来总结一下学到了什么吧：

1. 构造性思维: 面对“请构造一个……”类型的问题，不要害怕！通常解法都非常有规律。关键是找到一个简单、可扩展的“核心结构”，然后在其基础上进行修改，满足所有要求。这里的“脊椎”就是我们的核心结构！
2. 边界与极限分析: w <= 3b+1 这个不等式是解题的钥匙！通过思考一个元素最多能和多少个另一个元素相邻，我们找到了问题的可解性边界。先判断无解情况，可以大大简化后续的构造逻辑。
3. 对称性大法: w >= b 和 b > w 的情况其实是镜像的。只要解决了其中一个，另一个只需要稍微修改一下初始条件（比如换个起点的颜色）就可以啦。这能帮我们节省很多思考和编码的时间。
4. 坐标偏移技巧: 在棋盘或网格问题中，如果坐标范围很大，可以选一个远离原点的大坐标作为你的“世界中心”，这样就不用担心坐标变成负数或0，让计算更清爽。

希望这次的题解对你有帮助哦！继续努力，你一定能成为超厉害的算法大师的，喵~！如果有其他问题，随时可以再来找我玩！