G. ABBC or BACB
贪心
举个例子:BAAAA,BAAAAA,答案是A的总数
注意点:在连续的A中插入B,如:AAABABAA,AAABAA。很明显答案是A的总数减去最小的连续A的个数
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int a[15];
void sovle() {
string s;
cin >> s;
int n=s.length();
int tot=count(s.begin(),s.end(),'A');//查询A的数量
if(tot==n||tot==0){//特判
cout<<"0\n";
return ;
}
if(s[0]=='A'&&s[n-1]=='A'){
int f=1;
for(int i=0;i<n-1;i++) {
if(s[i]=='B'&&s[i+1]=='B'){
f=0;
break;
}
}
if(f){
int last=-1,mn=1e9,sum=0;
for(int i=0;i<n;i++){
if(s[i]=='A') sum++;
else mn=min(mn,sum),sum=0;
}
mn=min(mn,sum);
tot-=mn;
}
}
cout << tot << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
sovle();
}
return 0;
}