← 返回题目列表

AtCoder · agc065_c

C. 避免半额

中文机器翻译题面 查看原题

分数: 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 满足条件。