题解：CF2068J The Ultimate Wine Tasting Event

· · 题解

首先每个字母都必须换一次，显然前 n 个字母中的 R 必须要和后 n 个字母中的 W 交换，我们发现前 n 个字母中的 W 不可能换到后面，于是可以把前一半 W 放到第一个集合，后一半 W 放到第二个集合，此时可以把个数为奇数的不合法情况判掉，由于集合元素是递增的，如果前一半 W 还没放完就出现了 R 显然不合法，后 n 个字母中的 R 操作方式同理，如果后一半 R 放的时候有一个 W 插在中间也不合法。时间复杂度 O\left ( n \right ) 。

#include<bits/stdc++.h>
#define pb push_back
#define ls x<<1
#define rs x<<1|1
#define vt vector<int>
#define ll long long
#define pp pair<ll,ll>
#define N 110
#define ull unsigned long long
using namespace std;
const ll M=998244353;
const ll inf=1e18;
int n;
string s;
void add(ll &x,ll y) { if((x+=y)>=M) x-=M; }
void add(ll &x,ll y,ll z) { x=(x+y*z%M)%M; }
ll qm(ll x,ll y) {
    ll res=1;
    for(;y;x=x*x%M,y/=2) if(y&1) res=res*x%M;
    return res;
}
void solve() {
    cin>>n>>s;int s1=0,s2=0;s=' '+s; bool f=0;   
    for(int i=1;i<=n;i++) s1+=(s[i]=='W');
    if(s1&1) {
        printf("NO\n");
        return ;
    } 
    for(int i=1;i<=n;i++) 
        if((s2+=(s[i]=='W'))<s1/2&&s[i]=='R') {
            printf("NO\n");
            return ;
        }
    s1=0;s2=0;
    for(int i=n+1;i<=2*n;i++) s1+=(s[i]=='R');
    if(s1&1) {
        printf("NO\n");
        return ;
    }
    for(int i=n+1;i<=2*n;i++)  
        if((s2+=(s[i]=='R'))>s1/2&&s[i]=='W') {
            printf("NO\n");
            return ;
        }
    printf("YES\n");
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);int t=1;cin>>t;
    while(t--) { solve(); }
    return 0;
}