526互联

Codeforces Round 674 (Div. 3) B. Symmetric Matrix

发布时间 2023-10-13 22:35:50作者: zsxuan

有 \(n\) 块 \(2 \times 2\) 的瓷砖，瓷砖上的每个方格包含一个数字，每种瓷砖都有无数种。现在需要用所给瓷砖构造一个 \(m \times m\) 的方形矩阵 \(a\) 满足：

  • 每块瓷砖都在方形矩阵内
  • 瓷砖之间不能存在覆盖
  • \(a_{i, j} = a_{j, i}\) 。

输出是否存在这种构造。

一：显然合法的 \(m\) 满足 \(2 | m\) 才能保证能被瓷砖构造。

二：\(a_{i, j} = a_{j, i}\) 代表 \(a_{i, j}\) 根据直线 \(f(i) = j\) 对称。

假设一块瓷砖上的数字为 \(c_{i, j}\) 。当我们只选取一块瓷砖时，\(c_{1,1}\) 和 \(c_{2, 2}\) 一定满足对称关系。于是只需要存在一块瓷砖满足 \(c_{1, 2} = c_{2, 1}\) ，即可以使用这块瓷砖构造出方形矩阵。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n, m; std::cin>> n >> m;
	int ok = 0;
	for (int i = 0; i < n; i++) {
		int c[3][3];
		for (int j = 1; j <= 2; j++) for (int k = 1; k <= 2; k++) {
			std::cin >> c[j][k];
		}
		ok |= c[1][2] == c[2][1];
	}
	if (m % 2 == 0 && ok) std::cout << "YES\n";
	else std::cout << "NO\n";
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}