题目详解：B. Laura and Operations

问题描述

给定三个非负整数 $a, b, c$，分别表示数字 $1$、$2$、$3$ 的初始个数。
允许的操作：选择两个不同的数字（例如 $x$ 和 $y$），将它们擦除，然后写入与这两个数字都不同的第三个数字 $z$（$z \in \{1,2,3\}$ 且 $z \neq x, z \neq y$）。
问：经过若干次（包括零次）操作后，能否使黑板上只剩下数字 $1$？只剩下数字 $2$？只剩下数字 $3$？
对每个测试用例输出三个 $0/1$ 表示是否可行。

关键观察

每次操作会改变三个数字的个数：

• 选择数字 $1$ 和 $2$ → 擦掉一个 $1$ 和一个 $2$，写入一个 $3$。
  效果：$(a, b, c) \to (a-1, b-1, c+1)$。
• 选择数字 $1$ 和 $3$ → 擦掉一个 $1$ 和一个 $3$，写入一个 $2$。
  效果：$(a, b, c) \to (a-1, b+1, c-1)$。
• 选择数字 $2$ 和 $3$ → 擦掉一个 $2$ 和一个 $3$，写入一个 $1$。
  效果：$(a, b, c) \to (a+1, b-1, c-1)$。

不变量分析

考虑三个数的奇偶性（模 $2$ 的值）。
观察每次操作对奇偶性的影响：

• 操作 $(1,2)\to 3$：$a$ 减少 $1$（奇偶翻转），$b$ 减少 $1$（翻转），$c$ 增加 $1$（翻转）。
  三个数的奇偶性全部翻转。
• 操作 $(1,3)\to 2$：$a$ 减 $1$（翻转），$b$ 加 $1$（翻转），$c$ 减 $1$（翻转） → 三个奇偶性全部翻转。
• 操作 $(2,3)\to 1$：$a$ 加 $1$（翻转），$b$ 减 $1$（翻转），$c$ 减 $1$（翻转） → 三个奇偶性全部翻转。

因此每次操作后，三个数的奇偶性同时取反。换句话说，任意两个数奇偶性的相等关系保持不变：
如果开始时 $b$ 和 $c$ 奇偶相同，那么经过任意次操作后，$b$ 和 $c$ 仍然奇偶相同；如果开始时它们奇偶不同，那么永远不同。
同理，$(a,c)$ 和 $(a,b)$ 的奇偶相等关系也是不变量。

目标状态分析

假设我们想要最终只剩下数字 $1$，即最终状态为 $(a', b', c') = (n, 0, 0)$，其中 $n = a+b+c$（总个数不变，因为每次操作减少两个增加一个，总数减 $1$？等等：每次操作擦掉 $2$ 个数字，写入 $1$ 个数字，所以总数减少 $1$。初始总数为 $a+b+c$，经过 $k$ 次操作后总数为 $a+b+c - k$。最终只剩下一种数字，设其个数为 $m$，则 $m = a+b+c - k \ge 1$。因此最终个数 $m$ 可以是 $1, 2, \dots$，并不固定。但奇偶性分析仍然适用，因为最终状态中，其余两个数字个数为 $0$。

• 最终只剩 $1$：$b_{\text{final}} = 0$，$c_{\text{final}} = 0$。
  此时 $b$ 和 $c$ 的奇偶性都是 $0$（偶数），它们相同。
  根据不变量，初始的 $b$ 和 $c$ 必须奇偶相同。
• 最终只剩 $2$：$a_{\text{final}} = 0$，$c_{\text{final}} = 0$ → 初始 $a$ 和 $c$ 必须奇偶相同。
• 最终只剩 $3$：$a_{\text{final}} = 0$，$b_{\text{final}} = 0$ → 初始 $a$ 和 $b$ 必须奇偶相同。

充分性证明

上述奇偶相同条件是否也是充分的？是的，可以通过构造操作序列证明。

以只剩 $1$ 为例，假设 $b$ 和 $c$ 奇偶相同。
步骤 1：反复执行操作 $(2,3)\to 1$，即每次减少一个 $2$ 和一个 $3$，增加一个 $1$。只要 $b>0$ 且 $c>0$，就执行该操作。
经过若干次后，要么 $b=0$，要么 $c=0$（或同时为 $0$）。因为 $b$ 和 $c$ 奇偶相同，它们会同时变成 $0$（若 $b=c$），或者一个为 $0$ 另一个为偶数（因为同奇偶且差为偶数）。

• 若 $b=c=0$，已经只剩 $1$，完成。
• 否则，不妨设 $b>0$，$c=0$，且 $b$ 为偶数（因为同奇偶，$0$ 是偶数，所以 $b$ 也是偶数）。
  此时执行两次操作组合：
  ① 选择 $1$ 和 $2$ → 擦掉 $1$ 和 $2$，写入 $3$：$(a,b,c)\to(a-1, b-1, 1)$。
  ② 选择 $2$ 和 $3$ → 擦掉 $2$ 和 $3$，写入 $1$：$(a-1, b-2, 0)$。
  这两步合并效果：$b$ 减少 $2$，$a$ 不变（$a$ 先减 $1$ 后加 $1$），$c$ 恢复为 $0$。
  重复此组合 $\frac{b}{2}$ 次，最终 $b$ 变为 $0$，且 $c=0$，只剩下 $1$。

对于只剩 $2$ 或只剩 $3$ 的情况，构造完全对称。

结论

• 可以只剩 $1$ $\iff$ $b$ 与 $c$ 奇偶相同，即 $(b \bmod 2) = (c \bmod 2)$。
• 可以只剩 $2$ $\iff$ $a$ 与 $c$ 奇偶相同，即 $(a \bmod 2) = (c \bmod 2)$。
• 可以只剩 $3$ $\iff$ $a$ 与 $b$ 奇偶相同，即 $(a \bmod 2) = (b \bmod 2)$。

算法实现

对于每个测试用例，只需计算三个奇偶性比较并输出 $0/1$。
时间复杂度 $O(1)$ 每个测试用例，总复杂度 $O(t)$。

代码（C++）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int a, b, c;
        cin >> a >> b >> c;
        cout << ((b % 2 == c % 2) ? "1" : "0") << " ";
        cout << ((a % 2 == c % 2) ? "1" : "0") << " ";
        cout << ((a % 2 == b % 2) ? "1" : "0") << "\n";
    }
    return 0;
}

示例验证

• 输入 1 1 1：$b,c$ 奇偶相同 → 1；$a,c$ 相同 → 1；$a,b$ 相同 → 1 → 输出 1 1 1。
• 输入 2 3 2：$b=3,c=2$ 奇偶不同 → 0；$a=2,c=2$ 相同 → 1；$a=2,b=3$ 不同 → 0 → 输出 0 1 0。
• 输入 82 47 59：$b=47,c=59$ 同为奇数 → 1；$a=82,c=59$ 不同 → 0；$a=82,b=47$ 不同 → 0 → 输出 1 0 0。

与题目示例完全一致。