题解：AT_abc428_c [ABC428C] Brackets Stack Query

weifengzhaomi · 2025-10-20 22:17:05 · 题解

社区贡献掉了，赶紧写篇题解补补。

题目大意

就是每次操作会在末尾添加左括号和右括号以及删去最后一个字符，每次操作完后问题是不是合法字符串。

合法字符串的定义，这个大家应该都会，具体看题目。

暴力思路

这道题一眼下去很像每次操作用栈来判断是否是合法的，但是注意到复杂度为 O(n ^ 2)，无法通过。

正解思路

我们发现，当一个括号序列是合法的，长度应该是偶数，且每个左括号都有配对的右括号。

那么，我们用一个栈来存储当前未匹配的左括号和一个变量来存储当前的字符长度。

然后，我们按照题目操作来分类讨论。

1. 添加字符：

   • 若添加左括号：栈深度加一（新的未匹配左括号），长度也要加一。
   • 若添加右括号：若栈非空（有可匹配的左括号），则栈深度减一（有左括号可以匹配），长度加一；否则仅长度加一（都是右括号当然匹配不了啦）。

2. 删去字符：

   • 先记录被删除的字符和其位置。
   • 若删除左括号：若该左括号是未匹配的（在栈顶），则栈深度减一，长度减一。
   • 若删除右括号：若该右括号之前匹配过左括号（即删除前因它减少过栈深度），则栈深度加一（恢复被匹配的左括号），长度减一；否则仅长度减一。

当处理好之后，只要判断长度是否为 0 并且栈为空就好啦。

代码不放了。