题解：AT_abc428_c [ABC428C] Brackets Stack Query

Chiesl · 2025-10-19 16:57:07 · 题解

题意简述

你需要动态维护一个初始为空的括号序列。

有 m 次操作，每次操作为以下两种中的一种：

• 在序列的末尾添加一个 ( 或者 )。

• 删除序列末尾的一个括号，保证此时序列非空。

每次操作后你需要回答当前序列是否为一个合法的括号序列。

解题思路

我们考虑判断一个括号序列合法的充要条件是：

• 序列的长度为偶数（废话）。

• 序列中左括号的数量等于右括号的数量。

• 序列中任意一段前缀的左括号数量大于等于右括号数量。

前两个很显然，也是必要条件，加上第三个以后才算是充分条件，证明比较简单，此处不给出。

知道这个以后，就很容易维护了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 8e5 + 5;
char stk[N], c[3];
int n, m, cnt, sum[N];
int main () {
    scanf("%d", &m);
    for (int i = 1, op; i <= m; i++) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%s", c), stk[++n] = c[0];
            if (c[0] == '(') sum[n] = sum[n - 1] + 1;
            if (c[0] == ')') sum[n] = sum[n - 1] - 1;
            if (sum[n] < 0) cnt++;
        } else {
            if (sum[n] < 0) cnt--;
            n--;
        }
        if (!sum[n] && !cnt) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

时间复杂度：\operatorname{O}(m)。

感谢管理员神犇耐心看完，求过 qwq。