A. 樱子的考试 - 详细题解

问题重述

给定 $a$ 个 $1$ 和 $b$ 个 $2$，在每个数前添加正号或负号，问能否使整个数组的和为 $0$。

---

问题转化

在每个数前添加 $+$ 或 $-$，相当于将数组分成两个子集：

• 带正号的数放入集合 $P$
• 带负号的数放入集合 $N$

数组总和为 $0$ 等价于：

$$\sum_{x \in P} x = \sum_{x \in N} x$$

而所有数的总和为：

$$S = \sum_{x \in P} x + \sum_{x \in N} x = 2 \times \sum_{x \in P} x $$

因此，总和 $S$ 必须是偶数，且每个子集的和为 $\frac{S}{2}$。

---

必要条件分析

设 $a$ 个 $1$，$b$ 个 $2$，则总和为：

$$S = a \times 1 + b \times 2 = a + 2b$$

条件 1：总和为偶数

$$S = a + 2b \equiv a \pmod{2}$$

所以 $S$ 为偶数当且仅当 $a$ 为偶数。

结论：若 $a$ 是奇数，则直接输出 "NO"。

---

条件 2：能否凑出 $\frac{S}{2}$

当 $a$ 为偶数时，设 $a = 2k$，则：

$$\frac{S}{2} = \frac{a + 2b}{2} = \frac{2k + 2b}{2} = k + b $$

我们需要判断能否用若干 $1$ 和 $2$ 凑出 $k + b$。

关键观察：

• 每个 $2$ 可以看作两个 $1$ 的替代
• 我们实际上是在分配符号，等价于选择一部分数放在正号集合

---

分类讨论

情况 1：$b$ 为偶数

当 $b$ 为偶数时，可以将 $2$ 平均分成两组，每组 $\frac{b}{2}$ 个 $2$，和为 $b$。
再加上 $k$ 个 $1$ 到正号集合，就能得到 $k + b$。

结论：$b$ 为偶数时，答案为 "YES"。

---

情况 2：$b$ 为奇数

当 $b$ 为奇数时，无法将 $2$ 完全平分。
设 $b = 2m + 1$，则 $\frac{S}{2} = k + 2m + 1$。

将 $2$ 尽量平分：每组 $m$ 个 $2$，和为 $2m$，还剩下一个 $2$ 需要分配。

这个剩下的 $2$ 必须放在正号集合，此时正号集合的和为 $2m + 2$，还需要 $k - 1$ 个 $1$ 来凑成 $k + 2m + 1$。

因此，需要至少 $2$ 个 $1$（因为 $k \ge 1$ 才能有 $k - 1 \ge 0$，而 $k = \frac{a}{2}$，所以 $a \ge 2$）。

更简单的理解：

• $b$ 为奇数时，总和为 $a + 2b$ 是奇数？不对，$a$ 已经保证为偶数，所以总和是偶数
• 但奇数个 $2$ 意味着无法直接平分 $2$，需要用 $1$ 来平衡
• 若 $a = 0$，则没有 $1$ 可以调整，答案为 "NO"
• 若 $a \ge 2$（即至少有两个 $1$），则可以用两个 $1$（和为 $2$）替代一个 $2$，实现平衡

结论：$b$ 为奇数时

• 若 $a = 0$，答案为 "NO"
• 若 $a \ge 2$，答案为 "YES"

---

算法步骤

1. 读入 $a$（$1$ 的个数）和 $b$（$2$ 的个数）
2. 若 $a$ 为奇数，输出 "NO"
3. 否则（$a$ 为偶数）：
   • 若 $b$ 为偶数，输出 "YES"
   • 若 $b$ 为奇数：
     • 若 $a = 0$，输出 "NO"
     • 否则输出 "YES"

---

完整代码

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

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int cnt1, cnt2;
        cin >> cnt1 >> cnt2;
        
        if (cnt1 % 2 == 1) {
            cout << "NO" << endl;
        } else {
            if (cnt2 % 2 == 0) {
                cout << "YES" << endl;
            } else {
                if (cnt1 == 0) {
                    cout << "NO" << endl;
                } else {
                    cout << "YES" << endl;
                }
            }
        }
    }
    
    return 0;
}

---

时间复杂度

• 每个测试用例 $O(1)$
• 总复杂度 $O(t)$

---

示例验证

$a$	$b$	$a$ 奇偶	$b$ 奇偶	条件	输出
0	1	偶	奇且 $a=0$	NO
	3
2	0		偶	YES
	3		奇且 $a \ge 2$
3	1	奇	-	NO

与样例输出完全一致。