专栏文章

AT_abc428_c 题解

MMoya_Rao啾？啾！
AT_abc428_c题解参与者 8已保存评论 8

文章操作

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

当前评论
8 条
当前快照
1 份
快照标识符
@minkfy19
此快照首次捕获于
2025/12/02 03:52
3 个月前
此快照最后确认于
2025/12/02 03:52
3 个月前
查看原文
沦落到写 C Sol。
虽然但是对于一个只过了前两题的人来说写 C Sol 不过分对吧。
直接根据栈来判断很麻烦的，因为有删除操作。
但是可以考虑换一个角度，把 ( 看作 11，把 ) 看作 −1-1，那么判断条件就转化为，所有的加起来为 00，且对于任意前缀都不得为负。
考虑维护前缀 min⁡\min，以及其前缀和。这边为了方便直接拿了两个 stack mnmn 和 sumsum 来进行维护。
首先考虑加入的操作。很显然的，我们要往 sumsum 和 mnmn 里各塞一个东西。sumsum 里塞的东西很简单，就是这一轮新加的这个字符所对应的数字 xx 加上 sumsum 原本的栈顶的数字即可。而 mnmn 呢，由于算的是前缀 min⁡\min，因此应该是原来的栈顶与 sumsum 里塞进去的那个数字取 min⁡\min 的值。
然后考虑删除的操作。这太不要脑子了！我们直接让 sumsum 和 mnmn 分别弹出栈顶即可，因为最后那一位被删掉了，那么它维护的值也就作废了。
CPP
int opt=read();
if(opt==1){
    char c;cin>>c;
    int x=(c=='('?1:-1);
    int st=(sum.size()?sum.top():0);
    int mt=(mn.size()?mn.top():0);
    sum.push(st+x);
    mn.push(min(mt,st+x));
}else sum.pop(),mn.pop();
最后那就是判断啦！只有当 sumsum 的栈顶为 00，且 mnmn 的栈顶也为 00 的情况下，才是满足条件的哦。当然了，如果两个栈都是空的，那肯定也满足条件啦！
CPP
if(sum.empty())cout<<"Yes\n";
else if(!sum.top()&&!mn.top())cout<<"Yes\n";
else cout<<"No\n";
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！

评论

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

正在加载评论...