526互联

Codeforces Round 804 (Div. 2) B. Almost Ternary Matrix

发布时间 2023-09-10 20:32:33作者: zsxuan

给两个偶数 \(n\) 和 \(m\) 。任务是构造任意一个二进制矩阵，\(n \times m\) 。对于任意 \((i, j)\) ，有且仅有两个邻居的颜色与 \(a_{i, j}\) 不同。邻居的定义为 \(|x - x'| + |y - y'| = 1\) 。

观察：任何 \(n \times m\) 的矩阵若作为一个大型矩阵的子矩阵不会受到限制。于是构造大型矩阵。

性质1： 矩阵、网格构造性问题由小及大考虑。

  • 矩阵大小 \(1 \times 1\) 。
  • 矩阵大小为 \(2 \times 2\)

\[\begin{aligned} 01 \\ 10 \end{aligned} \]

和它的旋转矩阵，是唯一合法构造。

  • 矩阵大小为 \(4 \times 4\) ，构造题遵守稳定性原则，较优的方案是对 \(2 \times 2\) 的矩阵经过旋转拼接成 \(4 \times 4\) 。由于可控性强，不难枚举出以下构造合法。

\[\begin{aligned} 1001 \\ 0110 \\ 0110 \\ 1001 \end{aligned} \]

  • 矩阵大小为 \(8 \times 8\)
    强可控性下不难得到，将 \(4\) 个构造出的 \(4 \times 4\) 矩阵直接拼接即可合法。

  • 矩阵大小 \(2^x \times 2^x, (x \geq 2)\) ，推广使用四个 \(2^{x-1} \times 2^{x-1}\) 的矩阵拼接。

  • 不难观察到只有 \(n, m\) 都为偶数时，所构造出的子矩阵才合法。正好满足题意。

    • 即大概率奇数情况下是不存在合法情况的。

矩阵生成公式可以从两维独立的角度考虑。

  • 列上：\(j \% 4 = {0, 1}\) 时 \(g_{i, j} = 1\) ，否则 \(g_{i, j} = 0\) 。
  • 行上：\(i \% 4 = {2, 3}\) 时，\(reverse(g_i.begin, g_i.end)\) 。
view 
#include <bits/stdc++.h>
int g[55][55];
void solve() {
	int n, m; std::cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			std::cout << g[i][j] << " \n"[j==m];
		}
	}
}
signed main() {
	for (int i = 1; i <= 50 ; i++) {
		for (int j = 1; j <= 50; j++) {
			if (j % 4 == 1 || j % 4 == 0) g[i][j] = 1;
			else g[i][j] = 0;
		}
		if (i % 4 == 2 || i % 4 == 3) std::reverse(g[i] + 1, g[i] + 50 + 1);
	}
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}