E. 布尔博弈

    Type: Default 1000ms 256MiB

布尔博弈

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

未来教育的高材生小未和小来正在玩一个游戏。游戏中有一个由 nn 个布尔值组成的字符串,每个布尔值要么为true,要么为false,以长度为 nn 的二进制字符串 ∗^{\text{∗}} 表示(其中 1\texttt{1} 表示真, 0\texttt{0} 表示假)。最初,布尔值之间没有运算符。

小未和小来将轮流在布尔值之间放置 逻辑并(&&) 或 逻辑或(||) 运算符 ,小未先放。需要特别注意的是,运算过程中,逻辑并的优先级高于逻辑或。

一共有 nn 个布尔值,所以游戏将由 n−1n-1 个回合组成。小未的目标是最后的语句结果为 true,而小来的目标是最后的语句结果为 false。给定布尔值字符串,判断如果双方都以最佳方式放置运算符,小未是否会赢。

∗^{\text{∗}} 二进制字符串是指仅由字符 0\texttt{0} 和 1\texttt{1} 组成的字符串。

输入格式

第一行包含 tt ( 1≤t≤1041 \leq t \leq 10^4 ) - 测试用例数。

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

第二行包含长度为 nn 的二进制字符串,由字符 0\texttt{0} 和 1\texttt{1} 组成的二进制字符串。

保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5 。

输出格式

对于每个测试用例,如果小未获胜,则输出YES,否则输出 NO。

样例 #1

样例输入 #1

5
2
11
3
010
12
101111111100
10
0111111011
8
01000010

样例输出 #1

YES
NO
YES
YES
NO

【Wangzai月赛(入门组)】第一场

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2024-12-21 19:00
End at
2024-12-21 20:30
Duration
1.5 hour(s)
Host
Partic.
17