CF2147C Rabbits
题目描述
你有 n 个花盆依次排成一行，从左到右编号为 1 到 n。有些花盆里种有花，有些则是空的。你会得到一个二进制字符串 s，用于描述每个花盆是否有花（s_i = 1 表示有花，s_i = 0 表示空）。你还有一些兔子，现在你想为兔子和花一起拍一张漂亮的照片。你想在每个空花盆（s_i = 0）里放上一只兔子，对于每只兔子，你可以让它朝左或朝右。
不幸的是，这些兔子很淘气，它们会试图跳到其他花盆，这样会毁了照片。
每只兔子会准备朝它面对的方向跳向下一个花盆，但当以下任一情况发生时，它不会跳：
- 目标花盆里已有兔子；
- 有另一只兔子正朝相反方向准备跳向同一个目标花盆；
- 兔子准备跳出边界（比如位于第 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。
输出格式
对于每组测试用例，如果存在一种安排兔子的方案使得没有兔子会跳动，输出 “YES”；否则输出 “NO”。
输出不区分大小写，例如 “yEs”、”yes”、”Yes” 和 “YES” 都会被识别为肯定回答。
输入输出样例 #1
输入 #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
说明/提示
在第一个测试用例中，一种可行的方案为：第 1 个花盆放一只朝右的兔子，第 3 个花盆放一只朝左的兔子，第 4 个花盆放一只朝左的兔子。没有兔子会跳动，因为：
- 第 1 个花盆的兔子不会跳去第 2 个花盆，因为第 3 个花盆的兔子正朝左；
- 第 3 个花盆的兔子不会跳到第 2 个花盆，因为第 1 个花盆的兔子正朝右；
- 第 4 个花盆的兔子不会跳到第 3 个花盆，因为那里已经有兔子。
在第二个测试用例中，一种可行的方案为：第 1 个花盆放一只朝左的兔子，第 2 个花盆放一只朝右的兔子，第 3 个花盆放一只朝左的兔子。没有兔子会跳动，因为：
- 第 1 个花盆的兔子不会跳，因为左边是边界；
- 第 2 个花盆的兔子不会跳到第 3 个花盆，因为那里已有兔子；
- 第 3 个花盆的兔子不会跳到第 2 个花盆，因为那里已有兔子。
可以证明，第三个测试用例不存在任何有效方案。
思路
如果多个0相邻那么不用管，左右兔子封住，对着对方就可以了
如果0之间中间间隔了1，那么需要两个兔子；看着同一个花盆，一左一右，因为要一左一右，所以我们看作10为一节，最后遍历结果是0 10 10 ，如果这个节点分了三段，那么必然有一段会只能自己一个对着花盆
但这并不意味着不可行，如果他对着兔子是不能跳的，如果他对着墙是不能跳的，所以我们判断左右两端，重新分配
如果还不能分配就真不行了
代码
void solve() {
int n;string s;
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i]=='1')continue;
int cnt=0;
int j=i;
while(j+2<n&&s[j+1]=='1'&&s[j+2]=='0'){
j+=2;
cnt++;
}
bool l=(i>0&&s[i-1]=='1');
bool r=(j<n-1&&s[j+1]=='1');
if(l&&r&&cnt%2==0){
cout<<"NO"<<endl;
return ;
}
i=j;
}
cout<<"YES"<<endl;
}
