题解归档 - cf2225B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2225B
• 本地来源：problems/cf2225B/idea.md
• 题目链接：https://codeforces.com/contest/2225/problem/B
• 原始标题：cf2225B - Alternating String

思路

cf2225B - Alternating String

Represent each adjacent gap by whether the two characters are equal.

One operation chooses a substring, optionally flips all characters in it, then reverses it.

Invariant:

• Gaps strictly inside the chosen substring keep the same equal/different status, only their order is reversed.
• Gaps strictly outside the substring do not change.
• Only the two boundary gaps of the chosen substring can change.

Therefore all bad gaps must be among at most two boundaries, so bad <= 2 is necessary.

It is sufficient:

• bad = 0: already alternating.
• bad = 1: choose one endpoint character of that bad pair and flip it if needed.
• bad = 2: choose the substring between the two bad gaps; internal gaps are already good and the two boundaries can be fixed.

Answer: YES iff the number of adjacent equal pairs is at most 2.

代码

来源：problems/cf2225B/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        int bad=0;
        for(int i=1;i<(int)s.size();i++) bad+=s[i]==s[i-1];
        cout<<(bad<=2?"YES":"NO")<<"\n";
    }
    return 0;
}