题解：2024牛客暑期多校第5场——B [珑]

英文题干

You need to cover an rectangle using several 1×2 or 2×1 dominoes. Each position must be covered exactly once, and the dominoes must not extend outside the rectangle

Additionally, there may be two types of constraints:

1. The short sides of the dominoes cannot be adjacent, meaning no t wo dominoes can share a side of length 1.
2. The long sides of the dominoes cannot be adjacent, meaning no two dominoes can share a side of length 2 (even if they only share one edge).

There are T queries, each giving n,m,a,b, representing the size of the rectangle and whether the two constraints exist. When a is 0, the first constraint exists; when a is 1, the first constraint does not exist. When b is 0, the second constraint exists; when b is 1, the second constraint does not exist. For each query, you need to determine if there is a way to cover the entire rectangle.

Input:

The first line contains a positive integer .

The next lines each contain four integers .

Output:

For each query, output "Yes" or "No" indicating whether there is a way to cover the entire rectangle.

中文题干

你需要用多个 1×2 或 2×1 的多米诺骨牌来覆盖一个 的矩形。每个位置必须被覆盖一次，并且多米诺骨牌不能超出矩形的边界。

此外，可能会有两种类型的约束：

1. 多米诺骨牌的短边不能相邻，这意味着没有两个多米诺骨牌可以共享长度为 1 的边。
2. 多米诺骨牌的长边不能相邻，这意味着没有两个多米诺骨牌可以共享长度为 2 的边（即使它们只共享一个边）。

有 个查询，每个查询给出 ，表示矩形的大小以及这两个约束是否存在。当 a=0 时，第一个约束存在；当 a=1 时，第一个约束不存在。当 b=0 时，第二个约束存在；当 b=1 时，第二个约束不存在。对于每个查询，你需要确定是否有办法覆盖整个矩形。

思路

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 1010;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    while (T--) {
        int n, m, a, b;
        cin >> n >> m >> a >> b;
        if (n * m % 2 == 1) {
            cout << "No" << "\n";
            continue;
        }

        if (a == 1 && b == 1) {  // 无限制
            cout << "Yes" << "\n";
        }
        else if (a == 0 && b == 0) {  // 双限制
            if ((n == 1 && m == 2) || (n == 2 && m == 1)) {
                cout << "Yes" << "\n";
            }
            else {
                cout << "No" << "\n";
            }
        }
        else if (a == 1 && b == 0) {  // 限制长边
            if ((m == 1 && n % 2 == 0) || (m % 2 == 0 && n == 1)) {
                cout << "Yes" << "\n";
            }
            else {
                cout << "No" << "\n";
            }

        }
        else if (a == 0 && b == 1) {  // 限制短边
            if ((n == 1 && m != 2) || (n != 2 && m == 1)) {
                cout << "No" << "\n";
            }
            else {
                cout << "Yes" << "\n";
            }
        }
    }

    return 0;
}