AT_abc328_d [ABC328D] Take ABC 题解

_AyachiNene · 2023-11-12 08:12:55 · 题解

思路：

链表做法。这道题很好想到用链表做，找到一个可以删的位置连着往后面删两个就行了。还要注意一个细节，删完后向前跳要跳两次，因为可能有这种情况：

AABCBC

先前跳一次就只能删掉中间的 ABC，两次才能找到后面的 ABC。

Code:

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int f=1,res=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
    return res*f;
}
void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
struct node
{
    int nxt,pre;
    char val;
}e[114514*2];
void del(int x)
{
    e[e[x].pre].nxt=e[x].nxt;
    e[e[x].nxt].pre=e[x].pre;
}
string s;
int main()
{
    cin>>s;
    int n=s.size();
    s=' '+s;
    for(int i=1;i<=n;i++)
        e[i].pre=i-1,e[i].nxt=i+1,e[i].val=s[i];
    e[n].nxt=0;
    int head=n+1;
    e[head].nxt=1;
    e[1].pre=head;
    int i=head;
    while(i)
    {
//      cout<<i<<endl;
        if(e[i].val=='A'&&e[e[i].nxt].val=='B'&&e[e[e[i].nxt].nxt].val=='C')
        {
            for(int j=1;j<=3;j++)
            {
                del(i);
                i=e[i].nxt;
            }
            for(int j=1;j<=2&&i!=head;j++)
                i=e[i].pre;
        }
        else
            i=e[i].nxt;
    }
    for(int i=head;i;i=e[i].nxt)
        if(i!=head)
            cout<<e[i].val;
}