题解：CF2225B Alternating String

· · 题解

题解：CF2225B Alternating String

题目大意

给你一个仅由 a 和 b 组成的字符串，你可以进行之多一次一下操作：

  1. 选择一个至少由一个字符组成的字串。
  2. 将子串中的字符反转，即 a 变成 b，b 变成 a。你可以选择做或不做此操作。
  3. 将字串反转。此操作必做。

问能否将字符串变为交替字符串，定义交替字符串为没有相邻的字符是相同的。

思路

我们定义一组相邻字符相同为 S_i = S_{i-1}，所以三个相同字符算两组相邻字符相同。下文称连续字符。
我们手模几组样例就容易发现，如果只有一组连续字符，那这组字符前面的或者后面的都是符合条件的，所以我们只需要在它前面或者后面找一段操作即可。
如果有两组连续字符，可以发现这两组中间都是合法的，那我们只需要选出第一组的第二个字符和第二组的第一个字符再加上中间的那部分进行操作即可。
如果有超过两组你会发现一次操作最多只能解决两组连续字符，所以答案就是看连续字符的数量是否大于 2。

Code

#include <bits/stdc++.h>
using namespace std;

int t;
string s;

int read(){
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x*f;
}

int main(){
    t=read();
    while (t--){
        cin >>s;
        int cnt=0;
        for (int i=0;i<s.size();i++){
            if (s[i]==s[i-1])
                cnt++;
        }
        if (cnt>2)
            cout <<"NO"<<endl;
        else
            cout <<"YES"<<endl;
    }
    return 0;
}