# T678256 多米诺游戏 ## 题目背景 Alice 和 Bob 在一个 $n$ 行 $m...

Question

T678256 多米诺游戏

题目背景

Alice 和 Bob 在一个 $n$ 行 $m$ 列的网格上玩游戏，他们轮流放置 $1 \times 2$ 的多米诺骨牌（可以横放或竖放），Bob 先手。

Alice 的目标是尽量让网格被放满，Bob 的目标是尽量让网格不被放满。

骨牌不能重叠，也不能超出网格边界。

当网格被完全放满时，输出 Yes；如果网格没有被放满，但双方都无法再放置骨牌时，输出 No。

现在给定多组数据，请你判断每组数据的游戏结果。

题目描述

给定 $T$ 组数据，每组数据包含两个整数 $n$ 和 $m$ ，表示网格的行数和列数。

Alice 和 Bob 轮流在网格上放置 $1 \times 2$ 的多米诺骨牌，Bob 先手。

如果最终网格被完全放满，输出 Yes。
如果网格没有被放满，但双方都无法再放置骨牌，输出 No。

输入格式

第一行一个整数 $T$ ，表示数据组数。

接下来 $T$ 行，每行两个整数 $n, m$ 。

输出格式

共 $T$ 行，每行一个字符串 Yes 或 No，表示对应数据的游戏结果。

输入输出样例 #1

输入 #1

text
3
1 2
2 2
3 3

输出 #1

text
Yes
Yes
No

说明/提示

样例解释

对于 $1 \times 2$ 的网格，Bob 可以放一个骨牌占满整个网格，因此输出 Yes。
对于 $2 \times 2$ 的网格，Bob 先放一个骨牌（横放或竖放），Alice 可以在剩余空间放另一个骨牌，最终网格被放满，输出 Yes。
对于 $3 \times 3$ 的网格，总格子数为奇数，无法用 $1 \times 2$ 的骨牌完全覆盖，因此最终网格不会被放满，输出 No。

数据范围

$1 \le T \le 10^5$ , $1 \le n, m \le 10^{18}$ 。(请使用c++)

Answer 1

结论很简单：

如果 $n$ 和 $m$ 中至少有一个是偶数，答案是 Yes；
若二者都为奇数（总格数 $n\times m$ 为奇数），答案是 No。

证明思路

二者都奇数：总格数为奇数，不可能被 $1\times2$ 骨牌完全覆盖，必为 No。
至少一者为偶数：设有一维为偶数（例如 $m$ 为偶），Alice 采用镜像策略：以棋盘的竖直中轴为对称轴，Bob 下在哪两格，Alice 就在对称位置放置同样形状的骨牌。这样每一轮两人合起来恰好覆盖一对对称位置，最终能把棋盘铺满，故为 Yes。

代码（C++，O(T)）

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        long long n, m;
        cin >> n >> m;
        // 只需判断奇偶，不必相乘避免溢出
        if ((n & 1LL) && (m & 1LL)) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
        }
    }
    return 0;
}

说明：只判断奇偶即可，避免 $n \times m$ 溢出；范围 $n,m \le 10^{18}$ 用 long long 足够进行奇偶判断。