CF2029F 题解

· · 题解

如果这题往从一个合法区间通过两段乱跑的方式推到另一个合法区间的思路上面去想就没救了，应该从两个小朋友互相尝试接近对方的方向去想。

这样就启发我们去刁难小朋友，把它们放在一些恶心的位置。

Part 1：同时存在 RR 和 BB

把它们分别放在 RR 和 BB 中间，你会发现它们一步都走不了，就废了。返回无解。

下文中假设字符串中不存在 BB，只可能存在 RR。

Part 2：只有一段 R

显然不管我们怎么放小朋友，它们都肯定在一个同色的连续段内（包括端点），因此一定有解。

Part 3：存在两段长为偶数的 R 连续段

现在我们想象小朋友被困在 R 的连续段上面，需要通过 B 的桥梁移动以接近对方。注意到小朋友每一步都必须要走，所以我们只要让它们没法同时到达 B 旁边，它们就被困住了。

把第一个小朋友放在（长为偶数的 R）的端点处，第二个小朋友放在另一个长为偶数的 R 连续段的端点旁边一格，这样他们的位置奇偶性不同，没办法一起跨过 B。

Part 4：所有 R 连续段长度都为奇数

这样的话我们没法把小朋友困住了（R 连续段端点奇偶性不同）。

但这提供了另一个便利：（在初始位置不变的前提下）如果两个小朋友都在连续段的端点上，那么如果我们钦定一个小朋友的位置（是左端点还是右端点），另一个小朋友的位置也就固定了。

这就是说，如果第一个小朋友跨越 B 是顺时针的方向，那么我们可以控制第二个小朋友的初始位置，使得它必须往顺时针的方向走。这时，如果第一个小朋友尝试往逆时针走，第二个小朋友也只能往逆时针。

并且，走了一步之后，它们还在长度为奇数的连续段上，因此我们还能维持这个对应关系，两个小朋友走的方向还是相同的，因此它们永远无法追上对方。

返回无解。

Part 5：存在恰好一个长为偶数的连续段

此时仍然不会出现小朋友没法走出当前连续段的情况。

先假设它们在不同的长为奇数的连续段上。其余情况要么显然有解，要么可以走两步之后归约到这种情况。

首先把它们都移到端点上。

如果此时一个小朋友要往顺时针走，一个小朋友要往逆时针走，那么我们把它们都移到另一个端点上，就是一个往逆时针走一个往顺时针走，都是互相接近。这两种方式肯定有一种不经过偶数的连续段，这样走可以规避掉奇偶性不同的问题。

否则，让它们一直顺时针走直到有一个跑到偶数连续段上，此时，让偶数连续段上的小朋友往另一端走，奇数连续段上的那位反复横跳，这样当前者到达另一端准备顺时针继续走时后面那位还在原来的端点可以逆时针走，这样它们就可以相遇了。

因此这种情况有解。

至此我们完成了分讨，O(n) 跑几遍字符串就可以得出结果。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1000007;
ll T,n,fl;
char s[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>(s+1);s[fl=0]=s[n];
        for (int i=1;i<=n;++i) if (s[i]==s[i-1]){
            if (fl==0) fl=s[i];
            else if (fl!=s[i]) fl=-1;
        }
        if (fl==-1){
            cout<<"No\n";continue;
        }
        if (fl=='B') for (int i=0;i<=n;++i) s[i]='R'^'B'^s[i];
        ll cnt0=0,cnt1=0,pre=1,suf=n;
        while(s[pre]=='R'&&pre<=n) ++pre;
        if (pre>n){
            cout<<"Yes\n";continue;
        }
        while(s[suf]=='R') --suf;
        if (pre==suf){
            cout<<"Yes\n";continue;
        }
        if ((pre-1+n-suf)%2) cnt1=1;else cnt0=1;
        for (int i=pre+1,sum=0;i<=suf;++i){
            if (s[i]=='R') ++sum;
            else{
                if (sum&1) ++cnt1;else ++cnt0;sum=0;
            }
        }
        cout<<(cnt0==1?"Yes\n":"No\n");
    }
    return 0;
}