题解 AT4512 【[AGC030C] Coloring Torus】

CYJian · 2020-02-13 15:35:13 · 题解

首先，对于 k \leq 500，我们可以像下面这样无脑构造解：

k
1 1 1 ... 1
2 2 2 ... 2
3 3 3 ... 3
. . . ... .
. . . ... .
. . . ... .
k k k ... k

然后考虑 k > 500 怎么办。

用上面的办法肯定没法搞。考虑斜着填数：

1 2 3 4 ... n
2 3 4 ... n 1
3 4 ... n 1 2
4 ... n 1 2 3
. ... . . . .
. ... . . . .
. ... . . . .
n 1 2 . . . n-1

这样填出来也是合法的。考虑对这个下手：

比如一个 n=4 的矩阵：

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

我们考虑随便钦定一斜行，让它加入一个新数字，和原有的数字交替出现：

1 2 3 4
2 3 5 1
3 4 1 2
5 1 2 3

不难发现，这样也一定是合法的。然后我们还可以选择更多的斜行进行此操作。不难发现，我们用这个方法能加入的数字个数就是 2n 级别的，正好能完成题目的要求。

然后这题就做完了。