Codeforces Round 674 (Div. 3) 解题报告

CF1426B Symmetric Matrix

Codeforces Round 674 (Div. 3) 第二题,签到题。

题意翻译

  • 定义 \( m \times m \) 的矩阵为对称的当且仅当对于任意 \( i , j \in \left[ 1 , m \right] \),都有 \( s _ { i , j } = s _ { j , i } \)。
  • 给出 \( n \) 种大小为 \( 2 \times 2 \) 的矩阵和 \( m \),每种矩阵不限数量。若能用这些矩阵组成(不可旋转)\( m \times m \) 的对称矩阵,输出 YES,否则输出 NO
  • 输入格式:先输入数据组数 \( t \)。每组数据第一行为 \( n , m \),随后 \( 2 n \) 行描述了 \( n \) 种 \( 2 \times 2 \) 的矩阵,每个矩阵输入数据中依次为矩阵左上角、右上角、左下角、右下角。
  • 数据组数 \( t \leq 100 \),\( 1 \leq n , m \leq 100 \)。

题解

显然,只要存在一个对称的 \( 2 \times 2 \) 的矩阵,拿它堆叠必然能得到合法的答案。

所以只要注意判断 \( m \) 是奇数时无解即可。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

int n, m;

int main(void)
{
    int t;           //定义数据组数 t
    scanf("%d", &t); //读入数据组数 t
    while (t--)
    {
        scanf("%d%d", &n, &m); //读入小矩阵数量 n 和大矩阵边长 m
        reg bool f = false;
        for (reg int i = 1; i <= n; ++i)
        {
            static int a, b;
            scanf("%*d%d%d%*d", &a, &b); //这样读入可以空开第一个和第四个数
            f |= (a == b);               //是否对称
        }
        if ((m & 1) || !f) //m 为奇数或不存在对称的小矩阵时误解
            puts("NO");
        else //否则有解
            puts("YES");
    }
    return 0;
}
Pages: 1 2 3 4 5 6 7 8