题解：CF1992D Test of Love

SnapYust · 2024-07-16 21:33:57 · 题解

更好的阅读体验

这里

题目传送门

Test of Love

思路

模拟贪心，好像很多 Div3 的题都是这样。

先来个分类讨论，假设当前为 i，假设输入的字符串为 c，那么：

我们可以把 c_0 和 c_{n+1} 看作是个圆木。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
char c[200005];
void solve(){
    memset(c,0,sizeof(c));
    cin>>n>>m>>k;c[0]='L',c[n+1]='L';
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=0;i<=n+1;){
        bool b=0;
        if(i==n+1){cout<<"YES"<<endl;return;}
        if(c[i]=='W'){
            for(int j=i+1,l=1;j<=n+1;l++,j++){
                if(c[j]=='C'){cout<<"NO"<<endl;return;}
                if(c[j]=='L'){
                    k-=l;
                    if(k<0){cout<<"NO"<<endl;return;}
                    i=j;break;
                }
            }
            continue;
        }
        for(int j=min(i+m,n+1);j>=i+1;j--)if(c[j]=='L'){i=j;b=1;break;}
        if(b)continue;
        for(int j=min(i+m,n+1);j>=i+1;j--)if(c[j]=='W'){i=j;b=1;break;}
        if(b)continue;
        cout<<"NO"<<endl;return;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;while(t--)solve();
    return 0;
}