题解：AT_abc428_c [ABC428C] Brackets Stack Query

只有一种括号类型的合法括号序列其实有一种冷门的方法来判断：

对于每一个字符，若它为 (，那么视它为

1

，否则视为

-1

，然后做前缀和数组，设它是

a

，那么

1 \sim n

是合法括号序列当且仅当：

a_i = 0,\sum_{j = 1}^{i-1} [a_j<0] = 0

稍微研究就能发现这是对的。

然后对于这道题，直接用栈搞肯定是不好搞的，又看到括号类型只有一种，所以考虑使用上述方法，你发现插入都在尾部，删除也在尾部，并且操作贡献可还原（差分），于是直接维护

a_n

就行了，该加就加，该减就减，

n

是当前

S

的长度，也就是

|S|

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 8e5+5;
char s[N];
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int _;
	cin >> _;
	int sum = 0,cnt = 0,n = 0;
	while(_--)
	{
		int opt;
		cin >> opt;
		if(opt == 1)
		{
			char c;
			cin >> c;
			sum+=(c == '('?1:-1);
			if(sum<0)
			{
				++cnt;
			}
			s[++n] = c;
		}
		else
		{
			if(sum<0)
			{
				--cnt;
			}
			char c = s[n];
			--n;
			sum-=(c == '('?1:-1);
		}
		cout << (sum||cnt?"No\n":"Yes\n");
	}
	return 0;
}

题解：AT_abc428_c [ABC428C] Brackets Stack Query

文章操作

相关推荐

评论

题解：AT_abc428_c [ABC428C] Brackets Stack Query