题解：CF2147C Rabbits

Lucas_Fan_2013 · 2026-11-10 17:01:29 · 题解

思路

提供一种朴素的做法。

考虑兔子不跳跃的情况。

（2 表示讨论的兔子，1 表示其他的兔子，0 表示花盆）

情况一：21（同理，12）

情况二：201（同理，102）

所以，一只兔子如果不跳跃，那么它处于以下状态之一：

1. 必须向左看（不能向相反的方向看）

2. 必须向右看（同上）

3. 可以向左看或可以向右看

其中，状态 1 和状态 2 受另一个兔子所看方向的影响（属于情况二），而状态 3 不受（情况一）。

我们可以从左往右扫，每次遇到是兔子就依次判断是否满足状态 3 和状态 1 和状态 2。（状态 1 和状态 2 顺序无所谓）

状态 3 不考虑身边的兔子向哪边看，所以要先判断。

编号为 1 或 n 的兔子可以不判，向边界看就可以。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int t;
int n;
char a[N];
int zt[N]; // 每个兔子的状态，其中0表示不是兔子
signed main(){
    cin>>t;
    while (t--){
        cin>>n;
        bool f=true;
        for (int i=1;i<=n;i++) cin>>a[i],zt[i]=0;
        zt[1]=3,zt[n]=3,a[n+1]=0,a[0]=0;
        for (int i=2;i<n;i++){
            if (a[i]=='1') continue;
            if (a[i-1]=='0') zt[i]=3;
            else if (a[i+1]=='0') zt[i]=3;
            else if (a[i-2]=='0' and zt[i-2]!=1){
                if (zt[i-2]==3) zt[i]=3;
                else zt[i]=1;
            }
            else if (a[i+2]=='0') zt[i]=2,zt[i+2]=1;
        }
        for (int i=2;i<n;i++) if (a[i]=='0' and zt[i]==0){f=false;break;}
        if (f==true) cout<<"YES";
        else cout<<"NO";
        cout<<"\n";
        fflush(stdout);
    }
    return 0;
}