B4218 [常州市赛 2023] ABC 字符串 题解

· · 题解

题意

在一个只含有 A,B,C 的字符串中，最多可以操作几次，将 ABC 调换成 BCA。

思路

操作的本质其实就是将 A 往后移动两位，BC 为整体向前移动，只需要考虑一种情况，将 BC 看为一个整体 X，当左边有多个 A 右边有一个 BC 时。

例如 AAAX 会变成 XAAA 所以同理若左边有多个 A 且右边有多个 X 时就会依次从 AAAXX 变成 XAAAX 再变成 XXAAA 那么这道题就结束了。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e6+5,mod=998244353;
string s;
ll cnt,ans;
signed main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(i+1<s.size() && s[i]=='B' && s[i+1]=='C'){
            ans+=cnt;
            i++;
        }else if(s[i]=='A') cnt++;
        else cnt=0;
    }
    cout<<ans;
    return 0;
}