分数: 900 点
问题陈述
给你一个非负整数序列 A=(A_1,A_2,\dots,A_N) 长度 N。在这里, S=\sum_{i=1}^{N} A_i 是偶数。
判断是否存在一对长度为非负整数的序列 N, B=(B_1,B_2,\dots,B_N) 和 C=(C_1,C_2,\dots,C_N),满足以下条件:
- B_i+C_i=A_i 为 i=1,2,\dots,N.
- \sum_{i=1}^{N} X_i \neq \frac{S}{2} 对于每个整数序列 X=(X_1,X_2,\dots,X_N) 长度 N 其中 X_i=B_i or X_i=C_i 为 i=1,2,\dots,N.
解决 T 测试用例。
约束
- 1 \leq T
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- \sum_{i=1}^{N} A_i 是偶数。
- 总和 N 单个输入中的所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印 T 行。的 i- 第行应包含 Yes 如果有一对序列 B 和 C 满足条件 i- 第一个测试用例,以及 No 否则。
示例输入 1
3 3 1 2 3 6 1 1 2 2 3 3 4 1 1 1000000000 1000000000
示例输出 1
Yes No Yes
对于第一个测试用例, B=(1,1,3) 和 C=(0,1,0) 满足条件。
对于第二个测试用例,没有对 B 和 C 满足条件。