题解 CF1428C 【ABBB】

pigstd · 2020-10-21 13:16:39 · 题解

貌似用的都是栈的方法，其实本题也可以用链表做。

很容易想到一个显然的贪心：先从后往前删去 \text{AB} ，然后再从后往前删去 \text{BB}。

但是删去了之后怎么维护呢？用双向链表维护就可以了。

用 l_i 表示 i 下一个的字母的下标，r_i 表示 i 上一个字母的下标，那么显然删去 i 和 i+1 时，令 l_{r_i}=l_{l_i},r_{l_i}=r_{r_i} 就可以了。

code：

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

const int M=2e5+10;
int T,l[M],r[M],vis[M];
char s[M];

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>s+1;int n=strlen(s+1);int ans=0;
        for (int i=1;i<=n;i++)vis[i]=0,l[i]=i+1,r[i]=i-1;
        for (int i=n-1;i>=1;i--)
            if (!vis[i]&&!vis[l[i]]&&s[i]=='A'&&s[l[i]]=='B')
            {
                ans+=2;
                l[r[i]]=l[l[i]];
                r[l[i]]=r[r[i]];
                vis[i]=vis[l[i]]=1;
            }
        for (int i=n-1;i>=1;i--)
            if (!vis[i]&&!vis[l[i]]&&s[i]=='B'&&s[l[i]]=='B')
            {
                ans+=2;
                l[r[i]]=l[l[i]];
                r[l[i]]=r[r[i]];
                vis[i]=vis[l[i]]=1;
            }
        cout<<n-ans<<endl;
    }
    return 0;
}