专栏文章

题解：AT_abc428_c [ABC428C] Brackets Stack Query

CChiesl
AT_abc428_c题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minkamas
此快照首次捕获于
2025/12/02 03:48
3 个月前
此快照最后确认于
2025/12/02 03:48
3 个月前
查看原文

题意简述

你需要动态维护一个初始为空的括号序列。
有 mm 次操作，每次操作为以下两种中的一种：
  • 在序列的末尾添加一个 ( 或者 )。
  • 删除序列末尾的一个括号，保证此时序列非空。
每次操作后你需要回答当前序列是否为一个合法的括号序列。

解题思路

我们考虑判断一个括号序列合法的充要条件是：
  • 序列的长度为偶数（废话）。
  • 序列中左括号的数量等于右括号的数量。
  • 序列中任意一段前缀的左括号数量大于等于右括号数量。
前两个很显然，也是必要条件，加上第三个以后才算是充分条件，证明比较简单，此处不给出。
知道这个以后，就很容易维护了。

代码

CPP
#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;
}
时间复杂度：O⁡(m)\operatorname{O}(m)。
感谢管理员神犇耐心看完，求过 qwq。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...