CF1988B Make Majority

题目描述

给定一个序列 $[a_1,\ldots,a_n]$ ，其中每个元素 $a_i$ 只能是 $0$ 或 $1$ 。你可以对该序列进行若干次（也可以不进行）操作。每次操作，你可以选择两个整数 $1\le l\le r\le |a|$ （其中 $|a|$ 表示当前序列 $a$ 的长度），并将 $[a_l,\ldots,a_r]$ 替换为一个元素 $x$ ，其中 $x$ 是 $[a_l,\ldots,a_r]$ 的“多数元素”。

这里，“多数元素”定义如下：假设该区间内有 $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

输入 #1

输出 #1

No
Yes
No
Yes
No

说明/提示

在样例的第四组测试数据中，初始序列为 $a=[1,0,0,0,0,0,0,0,1]$ 。一种可行的操作序列如下：

选择 $l=2,r=8$ 并进行操作，此时 $a$ 变为 $[1,0,1]$ 。
选择 $l=1,r=3$ 并进行操作，此时 $a$ 变为 $[1]$ 。

由 ChatGPT 4.1 翻译

#CF1988B. Make Majority

Make Majority