← 返回题目列表

Codeforces · 2030/C

C. 一场真正的战斗

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

Alice 和 Bob 正在玩游戏。有一个 $$$n$$$ 布尔值列表,每个布尔值要么为真,要么为假,以长度为 $$$n$$$ 的二进制字符串 $$$^{\text{∗}}$$$ 给出(其中 $$$\texttt{1}$$$ 表示 true,$$$\texttt{0}$$$ 表示 false)。最初,布尔值之间没有运算符。

Alice 和 Bob 将轮流放置和/或在布尔值之间,Alice 首先进行。因此,游戏将由 $$$n-1$$$ 回合组成,因为存在 $$$n$$$ 布尔值。 Alice 的目标是最终语句评估为 true,而 Bob 的目标是评估为 false。给定布尔值列表,确定如果两个玩家都发挥最佳状态,Alice 是否会获胜。

要计算最终表达式,请重复执行以下步骤,直到语句包含单个 true 或 false:

- 如果语句包含 and 运算符,请选择任意一个并将其周围的子表达式替换为其计算结果。
- 否则,该语句包含 or 运算符。选择任意一个并将 or 周围的子表达式替换为其计算值。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 字符串的长度。

第二行包含长度为 $$$n$$$ 的二进制字符串,由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ - 布尔值列表组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果 Alice 获胜,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yES”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

5
2
11
3
010
12
101111111100
10
0111111011
8
01000010

输出 #1

YES
NO
YES
YES
NO

注意

在第一个测试用例中,Alice 可以将 和 放在两个布尔值之间。由于没有其他地方可以放置运算符,游戏结束,爱丽丝获胜,因为 true 和 true 都是 true。

在第二个测试用例中,Alice 可以将 or 放置在中间 true 和左侧 false 之间。 Bob 可以将 和 放置在中间 true 和右侧 false 之间。假或真又假的陈述是假的。

请注意,这些示例可能不是 Alice 或 Bob 的最佳策略。