[Atcoder AGC030C]Coloring Torus

题目大意：有$k$种颜色，要求构造出一个$n\times n$的矩阵，填入这$k$种颜色，满足对于每一种颜色，其中填充这种颜色的每一个方格，满足其相连的四个格子的颜色的个数和种类相同（对于每一种颜色而言，即不同颜色之间没有关系）。要求$n\leqslant500$。$k\leqslant 1000$

题解：这个真的只能看题解，题解神仙

先考虑$k=4a(a\in\mathbb{N^*}）$，令$n=\dfrac k2$，$(x,y)$填的数为：当$x\equiv0\pmod2$是时为$(x+y)\bmod n$，否则为$n+((x+y)\bmod n)$。

然后题解说，其他情况时，令$n=2\left\lceil\dfrac n4\right\rceil$，构造出$k=2n$时的答案，然后把所有大于$k$的数减去$n$就是答案。

卡点：无

C++ Code：

#include <cstdio>

#include <iostream>

int n, k;

int main() {

	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

	std::cin >> k;

	if (k == 1) { std::cout << "1\n1\n"; return 0; }

	std::cout << (n = k + 3 >> 2 << 1) << '\n';

	for (int i = 0; i < n; ++i, std::cout.put('\n'))

		for (int j = 0, t; j < n; ++j)

			t = (i + j) % n + 1 + (i & 1) * n,

			std::cout << (t > k ? t - n : t) << ' ';

	return 0;

}

巴特西

[Atcoder AGC030C]Coloring Torus

最新文章

热门文章