ABC328D题解

qqqaaazzz_qwq · 2023-11-11 22:02:38 · 题解

花了我35分钟才做出来。

考虑用链表来维护未删去的字符，指针从左往右扫，如果扫到一个完整的 \text{ABC}，就把这个 \text{ABC} 删掉，然后 i 往后跳两步。故使用链表维护。

#include <bits/stdc++.h>
using namespace std;
char s[200010];
int nxt[200010];
int lst[200010];
bool del[200010];
int n;

signed main()
{
    cin >> s;
    n = strlen(s);
    for (int i=n;i>=1;i--) s[i] = s[i-1];
    s[0] = 0;
    for (int i=1;i<=n;i++)
    {
        lst[i] = i-1;
        nxt[i] = i+1;
    }
    nxt[0] = 1;
    int x = 1;
    while(x!=n+1)
    {
        if(s[x]=='A'&&s[nxt[x]]=='B'&&s[nxt[nxt[x]]]=='C')
        {
            int u = lst[x];
            int v = nxt[nxt[nxt[x]]];
            lst[v] = u;
            nxt[u] = v;
            del[x] = del[nxt[x]] = del[nxt[nxt[x]]] = true;
            x = lst[lst[x]];
        }
        else x = nxt[x];
    }
    for (int i=1;i<=n;i++)
    {
        if(!del[i]) cout << s[i];
    }
    return 0;
}