← 返回题目列表

Codeforces · 1499/B

B. 二进制删除

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

给定一个字符串 $$$s$$$,仅包含字符“0”或“1”。令 $$$|s|$$$ 为 $$$s$$$ 的长度。

你被要求选择一些整数 $$$k$$$ ($$$k > 0$$$) 并找到一个长度为 $$$k$$$ 的序列 $$$a$$$ ,使得:

- $$$1 \le a_1 < a_2 < \dots < a_k \le |s|$$$;
- $$$a_{i-1} + 1 < a_i$$$ 对于从 $$$2$$$ 到 $$$k$$$ 的所有 $$$i$$$。

位置 $$$a_1, a_2, \dots, a_k$$$ 处的字符被删除,其余字符在不改变顺序的情况下连接起来。因此,换句话说,序列 $$$a$$$ 中的位置不应该相邻。

令结果字符串为$$$s'$$$。如果对于从 $$$2$$$ 到 $$$|s'|$$$ $$$s'_{i-1} \le s'_i$$$ 的所有 $$$i$$$,$$$s'$$$ 被称为已排序。

是否存在这样一个序列 $$$a$$$ 使得结果字符串 $$$s'$$$ 已排序?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的唯一行包含一个字符串 $$$s$$$ ($$$2 \le |s| \le 100$$$)。每个字符要么是“0”,要么是“1”。

输出

对于每个测试用例,如果存在序列 $$$a$$$,则打印“YES”,这样删除位置 $$$a_1、a_2、\dots、a_k$$$ 处的字符并在不更改顺序的情况下连接这些部分会产生排序的字符串。

否则,打印“NO”。

您可以按照您想要的任何大小写打印每个字母(例如,字符串 yEs、yes、Yes 和 YES 都被识别为肯定答案)。

示例

输入 #1

5
10101011011
0000
11111
110
1100

输出 #1

YES
YES
YES
YES
NO

注意

在第一个测试用例中,您可以选择序列 $$$a=[1,3,6,9]$$$。从“10101011011”中删除下划线字母将产生一个已排序的字符串“0011111”。

在第二个和第三个测试用例中,序列已经排序。

在第四个测试用例中,您可以选择序列 $$$a=[3]$$$。 $$$s'=$$$ "11",已排序。

在第五个测试用例中,无法选择序列 $$$a$$$ 来对 $$$s'$$$ 进行排序。