题解：CF2254B Evanescent

fish_love_cat · 2026-08-09 21:25:11 · 题解

我们用 \texttt{a,b,c} 分别代表三种不同的字符。

如果存在 \texttt{aba} 这样的结构，那么一步操作可以把三个段合并成一个段，贡献 -2。

如果存在 \texttt{abc} 这样的结构，那么一步操作可以至少消灭一个段，贡献 -1。

然后没了，直接找结构并搜一遍初始段数，扫一遍就做完了，复杂度线性。

inline void solve(){
    int n;
    string s;
    cin>>n>>s;
    s=" "+s;
    int ans=1,sum=0;
    for(int i=2;i<n;i++)
    if(s[i]!=s[i-1]&&s[i]!=s[i+1]&&s[i-1]==s[i+1]){
        sum++;
        break;
    }
    for(int i=2;i<=n;i++)
    if(s[i]!=s[i-1])ans++;
    for(int i=2;i<n;i++)
    if(s[i]!=s[i-1]&&s[i]!=s[i+1]){
        sum++;
        break;
    }
    ans-=sum;
    cout<<ans<<'\n';
}
signed main(){
    int t=1;
    t=read();
    while(t--)solve();
    return 0;
}
// 越是想要留下的越留不下
// 越是抓不住的越是像花
// 春天在指尖融化 融化
// 只剩一点点微凉的疤

// 越是害怕失去的越失去吧
// 越是看不清的越是像 她
// 光在眼睑上轻踏 轻踏
// 然后消失在薄暮之下