AT_abc328_d Take ABC 题解

· · 题解

主要思路

因为题目中要求了，是从前往后查找，所以说方便了许多。

这道题我用的是链表，l_i 就表示 i 它的上一位，r_i 就表示 i 的下一位。因为我们会发现，如果出现了一次 ABC，那么就相当于在链表中删除这一段。为了方便，我们可以从前往后枚举 C 出现的位置，在看一看 l_i 是不是 B，l_{l_i} 是不是 A 即可。删除的时候就是让 r_{l_{l_i}} 为 r_i，l_{r_i} 为 l_{l_i}。

最后的答案我们可以从 0 开始，也可以从 n + 1 开始查找（注：这里的 n 指 s 的长度）。

好了，看代码吧。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); TI--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 2e5 + 5;
string s;
int l[N];
int r[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> s;
    for (int i = 0; i <= s.size(); i++) l[i] = i - 1, r[i] = i + 1;
    for (int i = 2; i < s.size(); i++) {
        if (s[i] != 'C') continue;
        int x = l[i];
        if (x == -1) continue;
        int y = l[x];
        if (y == -1) continue;
        if (s[x] == 'B' && s[y] == 'A') {
            l[r[i]] = l[y];
            r[l[y]] = r[i];
        }
    }
    string ans = "";
    int now = l[s.size()];
    while (now != -1) {
        ans += s[now];
        now = l[now];
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
    return 0;
}

谢谢观看