CF2030C A TRUE Battle

Alice 和 Bob 正在玩一个游戏。有一个长度为 $n$ 的布尔值列表，每个值要么为 true，要么为 false，用一个二进制字符串 $^{\text{∗}}$ 表示（其中 $\texttt{1}$ 表示 true，$\texttt{0}$ 表示 false）。初始时，布尔值之间没有任何运算符。 Alice 和 Bob 轮流在布尔值之间插入 and 或 or 运算符，Alice 先手。因此，整个游戏将进行 $n-1$ 轮，因为有 $n$ 个布尔值。Alice 的目标是让最终表达式的值为 true，而 Bob 的目标是让其为 false。给定布尔值列表，若双方都采取最优策略，判断 Alice 是否能获胜。 对最终表达式的求值方式如下：重复执行以下步骤，直到表达式只剩下一个 true 或 false： - 如果表达式中包含 and 运算符，任选一个 and，将其两侧的子表达式用其运算结果替换。 - 否则，表达式中只包含 or 运算符，任选一个 or，将其两侧的子表达式用其运算结果替换。 例如，表达式 true or false and false 的求值过程为 true or (false and false) $=$ true or false $=$ true。可以证明，任何复合表达式的结果都是唯一的。$^{\text{∗}}$ 二进制字符串是仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成的字符串。

第一行包含一个整数 $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" 都会被识别为正面回答）。

在第一个测试用例中，Alice 可以在两个布尔值之间插入 and 运算符。由于没有其他位置可插入运算符，游戏结束，Alice 获胜，因为 true and true 的结果为 true。 在第二个测试用例中，Alice 可以在左侧 false 和中间 true 之间插入 or 运算符。Bob 可以在中间 true 和右侧 false 之间插入 and 运算符。表达式 false or true and false 的结果为 false。 注意，这些例子中的策略未必是 Alice 或 Bob 的最优策略。 由 ChatGPT 4.1 翻译