【题解】2020牛客暑期多校训练营（第六场）Problem G

介绍一个简短的 G 题构造方案。

先特判无解的情况， $n = 1$ ， $k = 1$ 或 $k \nmid 2 n (n + 1)$ 。

注意到一个同色的环中必然存在一条边 $(i, j)$ ，使得它与 $(i + 1, j)$ 或 $(i, j + 1)$ 同色。

如图：

所以我们只需要保证同行 / 列没有两条相邻的边，且相邻两行 / 列同一列 / 行的边颜色不相同。

这是很好构造的，对于 $k \nmid n$ ，直接按 $1, 2, \ldots, k$ 顺序依次分配边权；对于 $k \mid n$ ，在偶数行 / 列上循环移 1 位即可。

时间复杂度是 $\mathcal{O}(n ^ 2)$ 。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>

int main() {
  int te; scanf("%d", &te);
  while (te--) {
    int n, k;
    scanf("%d %d", &n, &k);
    if (n == 1 || (2 * n * (n + 1)) % k != 0 || k == 1) {
      puts("-1");
      continue;
    }
    if (n % k == 0) {
      int c = 0;
      for (int i = 1; i <= 2 * (n + 1); ++i) {
        int last = c;
        for (int j = 1; j <= n; ++j) {
          last = last % k + 1;
          printf("%d%c", last, " \n"[j == n]);
        }
        c ^= 1;
      }
    } else {
      int last = 0;
      for (int i = 1; i <= 2 * (n + 1); ++i)
        for (int j = 1; j <= n; ++j) {
          last = last % k + 1;
          printf("%d%c", last, " \n"[j == n]);
        }
    }
  }
  return 0;
}