专栏文章

题解：AT_abc428_c [ABC428C] Brackets Stack Query

CCamellia2025
AT_abc428_c题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minkfow5
此快照首次捕获于
2025/12/02 03:52
3 个月前
此快照最后确认于
2025/12/02 03:52
3 个月前
查看原文
首先如果我们将左括号看成一，右括号看成负一，那么当当前前缀和值为零时，便是一个合法的序列。
但是还有一个问题，就是如果有某个位置前缀和为负的话，说明那里一定至少有一个右括号会失配，那么直接记录这个位置就好了。

code

CPP
#include <bits/stdc++.h>
using namespace std;

int len, lst, a[800010], sum[800010]; 

int main () {
	int q;
	cin >> q;
	while (q--) {
		int opt;
		char c;
		cin >> opt;
		if (opt == 1) cin >> c, a[++len] = (c == '(' ? 1 : -1), sum[len] = sum[len - 1] + a[len];
		else a[len--] = 0, lst = (len < lst ? 0 : lst);
		if (lst) cout << "No" << endl;
		else {
			if (sum[len] < 0) lst = len, cout << "No" << endl;
			else cout << (sum[len] ? "No" : "Yes") << endl;
		}
	}
	return 0;
}

评论

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

正在加载评论...