题解：AT_abc428_c [ABC428C] Brackets Stack Query

linjinkun · 2025-11-28 20:00:47 · 题解

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

对于每一个字符，若它为 (，那么视它为 1，否则视为 -1，然后做前缀和数组，设它是 a，那么 1 \sim n 是合法括号序列当且仅当：

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

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

代码：

#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;
}