开学补题（cf版）（第四周）

Problem - G - Codeforces

题意：给你一个字符串，里面只包含A或者B两个字符

然后给你两种操作，一种是把AB变成BC,另外一种是把BA变成CB

然后问你给定的字符串最多可以变多少次

题解：我们可以发现无论你怎么搞，都要消耗一个a，所以看看B的附近有多少个A就有几次

但是假如B不够多就不可以把A全部消耗掉

比如    AAABAAAA  这里我们可以发现我们只能搞4个要去掉前面最小的那一个

因为B的区间只有1   看成一个块A块有2，B只有1,所以不行必须去掉一个最小的

如果B块大于或者等于A块那答案就是A的总和了

所以统计块数，然后要么去掉最小块数A的数量，要么就是全部

#include <bits/stdc++.h>
//#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=16005,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=100003;
typedef pair<int,int> PII;


void solve()
{
    string s;
    cin>>s;
   int ans=0;
   int cnt=0,sum=0;
   int res=0;
   vector<int> a;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='A')
        {
            cnt++;
        }
        else
        {
            if(s[i-1]=='A' || s[i+1]=='A')
            {
                res++;
            }
            if(cnt)
            {
                a.push_back(cnt);
                sum+=cnt;
            }
            cnt=0;
        }
    }
    if(cnt) sum+=cnt,a.push_back(cnt);
    sort(a.begin(),a.end());
    if(res>=a.size())
    {
        cout<<sum<<endl;
    }
    else
    {
        cout<<sum-a[0]<<endl;
    }

}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}