← 返回题目列表

Codeforces · 1988/B

B. 占多数

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

给定一个序列 $$$[a_1,\ldots,a_n]$$$,其中每个元素 $$$a_i$$$ 要么是 $$$0$$$ 要么是 $$$1$$$。您可以对序列应用多个(可能为零)操作。在每个操作中,您选择两个整数 $$$1\le l\le r\le |a|$$$(其中 $$$|a|$$$ 是 $$$a$$$ 的当前长度)并用单个元素 $$$x$$$ 替换 $$$[a_l,\ldots,a_r]$$$,其中 $$$x$$$ 是大多数$$$[a_l,\ldots,a_r]$$$。

这里,由 $$$0$$$ 和 $$$1$$$ 组成的序列的大部分定义如下:假设序列中分别有 $$$c_0$$$ 0 和 $$$c_1$$$ 1。

- 如果$$$c_0\ge c_1$$$,则大多数是$$$0$$$。
- 如果$$$c_0<c_1$$$,则大多数是$$$1$$$。

例如,假设 $$$a=[1,0,0,0,1,1]$$$。如果我们选择 $$$l=1,r=2$$$,则结果序列将为 $$$[0,0,0,1,1]$$$。如果我们选择 $$$l=4,r=6$$$,则结果序列将为 $$$[1,0,0,1]$$$。

确定是否可以通过有限次数的运算得到 $$$a=[1]$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 4\cdot 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$)。

每个测试用例的第二行包含一个由 $$$0$$$ 和 $$$1$$$ 组成的字符串,描述序列 $$$a$$$。

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

输出

对于每个测试用例,如果可以使 $$$a=[1]$$$,则打印 YES。否则,打印NO。您可以在任何情况下输出答案(上限或下限)。例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应。

示例

输入 #1

5
1
0
1
1
2
01
9
100000001
9
000011000

输出 #1

No
Yes
No
Yes
No

注意

在示例的第四个测试用例中,最初 $$$a=[1,0,0,0,0,0,0,0,1]$$$。有效的操作顺序是:

1. 选择 $$$l=2,r=8$$$ 并应用操作。 $$$a$$$ 变为 $$$[1,0,1]$$$。
2. 选择$$$l=1,r=3$$$ 并应用该操作。 $$$a$$$ 变为 $$$[1]$$$。