「LAOI-8」近期我们注意到有网站混淆视听 题解

· · 题解

设 s 中有 x 个 CSP 子串和 y 个 LGR 子串，那么答案即为 \lceil\min(\frac{x}{2},\frac{y}{2})\rceil，即只更改一种类型的子串。

对于方案，以更改 LGR 为例，若为偶数，则两两配对交换，比如 LGRLGR 变为 GGRLLR；若为奇数，则将其中一个 LGR 变为 LRG。

//luogu uid:Anemones 736184
#include<bits/stdc++.h>
using namespace std;
signed main(){
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        int n=s.size();
        int t1=0,t2=0;
        for(int i=0;i<n-2;i++){
            if(s.substr(i,3)=="LGR") t1++;
            if(s.substr(i,3)=="CSP") t2++;
        }
        cout<<min(ceil(t1/2.),ceil(t2/2.))<<endl;
    }
    return 0;
}