ABC328D

HDS_Acenaphthylene · 2023-11-12 09:38:42 · 题解

看到题解区没有链表的，来写一发。

我们把字符串转化为一个链表，判断之后三个字符是否构成 ABC，如果构成，消除。此时之前的字符和之后的字符可能构成 ABC，所以要回退两个字符（ABABCC在消除 S_{3\dots5} 后要从 B 回退到头结点）。

#include<bits/stdc++.h>
using namespace std;
string s;
struct node{char c;int next, pre;}lst[200005];
char nxt(int idx, int t) {
    if(idx == 11451419)return 'F';
    if(t == 0)
        return lst[idx].c;
    return nxt(lst[idx].next, t - 1);
}
int main() {
    cin >> s;
    s = " " + s;
    for(int i = 0;i <= s.size() - 1;i ++){
        lst[i].c = s[i];
        lst[i].next = i + 1;
        lst[i].pre = i - 1;
        if(i == s.size() - 1)lst[i].next = 11451419;
        if(i == 0)lst[i].pre = 0;
    }
    for(int i = 0;i != 11451419;) {
        if(nxt(i, 1) == 'A' && nxt(i, 2) == 'B' && nxt(i, 3) == 'C' && nxt(i, 3) != 'F') {
            lst[i].next = lst[lst[lst[lst[i].next].next].next].next;
            if(lst[i].next != 11451419)
                lst[lst[i].next].pre = i;
            i = lst[i].pre;
            i = lst[i].pre;
        }
        else i = lst[i].next;
    }
    for(int i = lst[0].next;i != 11451419;i = lst[i].next)cout << lst[i].c;
    return 0;
}