GridColoring - 题解

标签与难度

标签: 构造, 网格图, 数学, 思维, 实现, 模运算难度: 1700

题目大意喵~

主人你好呀~ 这道题是说，我们有一个 $n \times n$ 的小方格组成的网格，还有 $k$ 种漂亮的颜色，喵~ 我们的任务是给网格的每一条边都染上一种颜色。但是呢，有三个严格的规矩要遵守哦：

公平第一！ 每一种颜色的使用次数必须完全相同。
拒绝单调！ 图中不能存在任何一个所有边颜色都相同的闭合环路（比如一个 $1 \times 1$ 小格子的四条边）。
色彩斑斓！ 任何一整行或者一整列的边（比如第一行的所有水平边，或者第一列的所有竖直边），都必须包含至少两种颜色。

我们需要找到一个满足所有条件的染色方案，并把它打印出来。如果找不到这样的方案，就要告诉人家一声 -1 啦~

这里的网格结构稍微有点特别哦。一个 $n \times n$ 的格子世界，其实有 $n+1$ 行水平边线和 $n+1$ 列竖直边线。每行水平边线有 $n$ 条边，每列竖直边线有 $n$ 条边。所以，水平边和竖直边各有 $(n+1) \times n$ 条，总共有 $2 \times n \times (n+1)$ 条边需要我们来染色呢，喵！

解题思路分析

这道题是一道典型的构造题，需要我们想出一个聪明的染色方法来满足所有条件，喵~ 面对这种问题，我们先从最基本的约束条件入手，看看哪些情况下肯定无解，把它们先排除掉！

第一步：分析无解情况

颜色平衡条件：题目要求所有 $k$ 种颜色使用次数相同。总共有 $2 \times n \times (n+1)$ 条边，所以每种颜色应该使用 $\frac{2 \times n \times (n+1)}{k}$ 次。如果总边数不能被 $k$ 整除，那肯定就没办法平均分配啦！所以，如果 $2 \times n \times (n+1)$ 不能被 $k$ 整除，直接输出 -1。
色彩斑斓条件：题目要求每一行/列的边至少有两种颜色。
- 如果 $k=1$ ，我们只有一种颜色，怎么可能满足这个条件呢？所以 $k=1$ 时无解。
- 如果 $n=1$ ，那么每行/列就只有一条边。一条边怎么可能拥有两种颜色嘛！所以 $n=1$ 时也无解。

总结一下，只要遇到 n == 1，k == 1，或者 (2 * n * (n + 1)) % k != 0，我们就可以理直气壮地告诉 lzr 这是不可能的，然后输出 -1 走猫步啦~

第二步：构造染色方案

排除了无解的情况，剩下的就一定有解吗？大概率是这样，我们来尝试构造一个万能的方案吧！

一个最简单、最无脑的想法就是按顺序给所有边染色，颜色从 $1$ 到 $k$ 循环使用。我们把所有水平边看成一个大数组，所有竖直边看成另一个，然后从头到尾填色。

当前颜色 = 1给所有水平边染色: H[i][j] = 当前颜色; 当前颜色 = (当前颜色 % k) + 1;给所有竖直边染色: V[i][j] = 当前颜色; 当前颜色 = (当前颜色 % k) + 1;

这个方法看起来很美，喵~

平衡性：因为总边数是 $k$ 的倍数，这样循环染色，每种颜色出现的次数自然是完全一样的。
无单色环：一个 $1 \times 1$ 的小格子由四条边构成：H[r][c], H[r+1][c], V[r][c], V[r+1][c]（这里用0-indexed）。在我们的顺序染色大法里，这些边的染色顺序是不同的，它们的颜色编号几乎不可能完全一样。比如 V[r][c] 和 V[r][c+1] 的颜色是紧挨着染的，颜色编号只差1（可能会因为模 $k$ 而回绕），只要 $k>1$ 它们就肯定不同色。所以一个格子的四条边不可能是同一种颜色。

那么，这个简单的顺序染色法有什么问题吗？我们再看看第三个条件：色彩斑斓。

对于行：一行水平边 H[i][0], H[i][1], ..., H[i][n-1]，它们的颜色是连续的 c, c+1, c+2, ...（对 $k$ 取模）。因为 $n>1, k>1$ ，所以肯定不止一种颜色。没问题！
对于列：一列水平边 H[0][j], H[1][j], ..., H[n][j] 呢？H[r][c] 的颜色由它在一维展开后的位置 r*n + c 决定。那么 H[r+1][c] 的位置是 (r+1)*n + c。它们的位置差了 n。
- 如果 $n$ 不是 $k$ 的倍数（n % k != 0），那么 color(H[r][c]) 和 color(H[r+1][c]) 就不会相同。这一列的颜色序列就是 c, c+n, c+2n, ... (对 $k$ 取模)，因为 n % k != 0，所以颜色会变化。
- 但是！ 如果 $n$ 恰好是 $k$ 的倍数（n % k == 0），那 n \equiv 0 \pmod k。color(H[r+1][c]) 的位置 (r*n + c + n) 和 color(H[r][c]) 的位置 (r*n + c) 对 $k$ 取模后是相等的！这意味着 H[0][j], H[1][j], H[2][j], ... 的颜色会完全一样！这就违反了“色彩斑斓”的规定，喵呜~

啊哈！我们找到了问题的关键！简单的顺序染色法只在 n % k != 0 时有效。那 n % k == 0 的时候该怎么办呢？我们需要一个新策略！

第三步：分情况讨论

情况一：n % k != 0 就像我们刚才分析的，简单的顺序染色法是完美的！我们只要依次为所有边填上 1, 2, ..., k, 1, 2, ... 就好啦。

情况二：n % k == 0 这时候我们需要一个更巧妙的结构。让我们试试一种基于坐标的染色法： color(i, j) = (i + j) % k + 1

我们用这个公式来给所有水平边 H[i][j] 和所有竖直边 V[i][j] 染色。我们来检查一下它是否满足所有条件：

平衡性：对于一个 $(n+1) \times n$ 的矩阵，由于 $n$ 是 $k$ 的倍数，在每一行中，j 从 $0$ 到 $n-1$ ，i+j 的值会经历 n/k 个完整的 $0, 1, ..., k-1$ 的循环（对 $k$ 取模）。所以每种颜色在每一行都出现 n/k 次。总共 $n+1$ 行，所以一种颜色在 H 矩阵中出现 $(n+1) \times (n/k)$ 次。V 矩阵同理。总次数为 $2 \times (n+1) \times n/k$ ，正好是总边数除以 $k$ 。完美平衡！
色彩斑斑：
- 行：H[i][j] 的颜色由 (i+j)%k 决定。对于固定的 i，j 在变，颜色序列是 (i)%k, (i+1)%k, ...，显然不是单色的。
- 列：对于固定的 j，i 在变，颜色序列是 (j)%k, (j+1)%k, ...，也不是单色的。太棒了！
无单色环：一个格子的四条边是 H[r][c], H[r+1][c], V[r][c], V[r+1][c]。
- 由于 H 和 V 的染色规则一样，我们主要看坐标。
- color(H[r][c]) = (r+c)%k+1
- color(H[r+1][c]) = (r+1+c)%k+1
- color(V[r][c]) = (r+c)%k+1
- color(V[r][c+1]) = (r+c+1)%k+1 这四个颜色分别是 C, C+1, C, C+1 (对 $k$ 进行模运算并加1后的结果)。因为 $k>1$ ，C 和 C+1 肯定不同。所以这四条边不可能是同一种颜色！

综上所述，我们找到了一个完美的方案：

先判断无解情况。
如果 n % k == 0，使用 color(i, j) = (i + j) % k + 1。
如果 n % k != 0，使用简单的顺序染色 color = (cur++) % k + 1。

这样就能解决所有问题啦，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    int n, k;
    std::cin >> n >> k;

    // 第一步：检查无解情况，喵~
    long long total_edges = 2LL * n * (n + 1);
    if (n == 1 || k == 1 || total_edges % k != 0) {
        std::cout << -1 << std::endl;
        return;
    }

    // 准备好存放水平边和竖直边颜色的二维数组
    // H[i][j] 是第 i 行水平边线上的第 j 条边 (0-indexed)
    // V[i][j] 是第 i 列竖直边线上的第 j 条边 (0-indexed)
    // 为了方便，我们这里把 V 也当成 (n+1) x n 的矩阵
    std::vector<std::vector<int>> horizontal_edges(n + 1, std::vector<int>(n));
    std::vector<std::vector<int>> vertical_edges(n + 1, std::vector<int>(n));

    if (n % k == 0) {
        // 情况一：n 是 k 的倍数，使用 (i+j)%k 的构造法
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j < n; ++j) {
                int color = (i + j) % k + 1;
                horizontal_edges[i][j] = color;
                vertical_edges[i][j] = color;
            }
        }
    } else {
        // 情况二：n 不是 k 的倍数，使用简单的顺序染色法
        int current_color_idx = 0;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j < n; ++j) {
                horizontal_edges[i][j] = current_color_idx % k + 1;
                current_color_idx++;
            }
        }
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j < n; ++j) {
                vertical_edges[i][j] = current_color_idx % k + 1;
                current_color_idx++;
            }
        }
    }

    // 打印结果，要按题目要求的格式哦
    // 先打印所有水平边的颜色
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << horizontal_edges[i][j] << (j == n - 1 ? "" : " ");
        }
        std::cout << std::endl;
    }
    // 再打印所有竖直边的颜色
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << vertical_edges[i][j] << (j == n - 1 ? "" : " ");
        }
        std::cout << std::endl;
    }
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: 我们需要填充两个大小为 $(n+1) \times n$ 的矩阵，并把它们打印出来。所有操作都是简单的遍历和赋值，所以总的时间复杂度是 $O(n^2)$ ，对于这道题的 $n$ 的范围来说是绰绰有余的，喵~
空间复杂度: 我们需要两个 $(n+1) \times n$ 的二维数组来存储边的颜色，所以空间复杂度是 $O(n^2)$ 。

知识点总结

这道题真是个很好的思维锻炼呢！我们从中可以学到：

构造性算法: 解决这类问题的核心是找到一个能满足所有条件的通用构造方法，而不是去暴力搜索。
情况分析: 很多时候，一个单一的构造方法并不能解决所有问题。通过分析简单构造的失败之处（比如我们的顺序染色法在 n % k == 0 时失败），可以引导我们找到需要分类讨论的关键条件。
模运算的妙用: 模运算 (%) 在构造周期性、满足特定分布的模式时非常强大。无论是 (cur++) % k 还是 (i+j) % k，都是利用模运算创造出符合要求的色彩分布。
从约束反推: 先分析问题的“硬约束”（比如必须整除、n和k的特殊值），可以快速筛掉无解情况，简化问题。

希望我的讲解对你有帮助哦！继续加油，算法的世界还有更多有趣的冒险在等着我们呢，喵~！

GridColoring - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：分析无解情况 ​

第二步：构造染色方案 ​

第三步：分情况讨论 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​