A16627. Rabbits
编程题
普及/提高-
知识点
题目描述
你有 $n$ 个花盆依次排成一行，从左到右编号为 $1$ 到 $n$。有些花盆里种有花，有些则是空的。你会得到一个二进制字符串 $s$，用于描述每个花盆是否有花（$s_i = 1$ 表示有花，$s_i = 0$ 表示空）。你还有一些兔子，现在你想为兔子和花一起拍一张漂亮的照片。你想在每个空花盆（$s_i = 0$）里放上一只兔子，对于每只兔子，你可以让它朝左或朝右。
不幸的是，这些兔子很淘气，它们会试图跳到其他花盆，这样会毁了照片。
每只兔子会准备朝它面对的方向跳向下一个花盆，但当以下任一情况发生时，它不会跳：
- 目标花盆里已有兔子；
- 有另一只兔子正朝相反方向准备跳向同一个目标花盆；
- 兔子准备跳出边界（比如位于第 $1$ 个花盆且朝左，或者位于第 $n$ 个花盆且朝右）。
你的目标是为每只兔子选择方向，使得没有任何兔子会真的跳动，好让你有足够时间拍照。你需要判断是否存在一种有效方案，让所有兔子都不会跳。
不幸的是，这些兔子很淘气，它们会试图跳到其他花盆，这样会毁了照片。
每只兔子会准备朝它面对的方向跳向下一个花盆，但当以下任一情况发生时，它不会跳：
- 目标花盆里已有兔子；
- 有另一只兔子正朝相反方向准备跳向同一个目标花盆；
- 兔子准备跳出边界（比如位于第 $1$ 个花盆且朝左，或者位于第 $n$ 个花盆且朝右）。
你的目标是为每只兔子选择方向，使得没有任何兔子会真的跳动，好让你有足够时间拍照。你需要判断是否存在一种有效方案，让所有兔子都不会跳。
输入格式
每组测试包含多组数据。第一行为测试用例数 $t$，$1 \leq t \leq 10^4$。
每组测试第一行为一个整数 $n$，$1 \leq n \leq 2 \times 10^5$。
第二行为一个长度为 $n$ 的二进制字符串 $s$，描述每个花盆是否有花。
保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
每组测试第一行为一个整数 $n$，$1 \leq n \leq 2 \times 10^5$。
第二行为一个长度为 $n$ 的二进制字符串 $s$，描述每个花盆是否有花。
保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
输出格式
对于每组测试用例，如果存在一种安排兔子的方案使得没有兔子会跳动，输出 "YES"；否则输出 "NO"。
输出不区分大小写，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。
输出不区分大小写，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。
输入输出样例
输入 #1
12 4 0100 3 000 8 11011011 5 00100 1 1 5 01011 2 01 7 0101011 7 1101010 5 11001 4 1101 9 001101100
输出 #1
YES YES NO YES YES YES YES YES YES YES NO NO
说明/提示
[可视化工具链接](https://codeforces.com/assets/contests/2147/C_2iM9A1dE03B4IrDfFG54.html)
在第一个测试用例中，一种可行的方案为：第 $1$ 个花盆放一只朝右的兔子，第 $3$ 个花盆放一只朝左的兔子，第 $4$ 个花盆放一只朝左的兔子。没有兔子会跳动，因为：
- 第 $1$ 个花盆的兔子不会跳去第 $2$ 个花盆，因为第 $3$ 个花盆的兔子正朝左；
- 第 $3$ 个花盆的兔子不会跳到第 $2$ 个花盆，因为第 $1$ 个花盆的兔子正朝右；
- 第 $4$ 个花盆的兔子不会跳到第 $3$ 个花盆，因为那里已经有兔子。
在第二个测试用例中，一种可行的方案为：第 $1$ 个花盆放一只朝左的兔子，第 $2$ 个花盆放一只朝右的兔子，第 $3$ 个花盆放一只朝左的兔子。没有兔子会跳动，因为：
- 第 $1$ 个花盆的兔子不会跳，因为左边是边界；
- 第 $2$ 个花盆的兔子不会跳到第 $3$ 个花盆，因为那里已有兔子；
- 第 $3$ 个花盆的兔子不会跳到第 $2$ 个花盆，因为那里已有兔子。
可以证明，第三个测试用例不存在任何有效方案。
在第一个测试用例中，一种可行的方案为：第 $1$ 个花盆放一只朝右的兔子，第 $3$ 个花盆放一只朝左的兔子，第 $4$ 个花盆放一只朝左的兔子。没有兔子会跳动，因为：
- 第 $1$ 个花盆的兔子不会跳去第 $2$ 个花盆，因为第 $3$ 个花盆的兔子正朝左；
- 第 $3$ 个花盆的兔子不会跳到第 $2$ 个花盆，因为第 $1$ 个花盆的兔子正朝右；
- 第 $4$ 个花盆的兔子不会跳到第 $3$ 个花盆，因为那里已经有兔子。
在第二个测试用例中，一种可行的方案为：第 $1$ 个花盆放一只朝左的兔子，第 $2$ 个花盆放一只朝右的兔子，第 $3$ 个花盆放一只朝左的兔子。没有兔子会跳动，因为：
- 第 $1$ 个花盆的兔子不会跳，因为左边是边界；
- 第 $2$ 个花盆的兔子不会跳到第 $3$ 个花盆，因为那里已有兔子；
- 第 $3$ 个花盆的兔子不会跳到第 $2$ 个花盆，因为那里已有兔子。
可以证明，第三个测试用例不存在任何有效方案。