题解：AT_abc428_c [ABC428C] Brackets Stack Query

chu_yh · 2025-10-19 17:00:16 · 题解

简单的括号匹配问题，这里介绍不用栈的方法。

挨个处理操作。把字符串的 ( 当成 1，) 当成 -1，照此转化为数组。那么容易处理出当前字符串转换后的元素和 sum。显然，若 sum \ne 0 时，答案一定为 No。

显然，就算在 sum=0 的情况下，若当前字符串转化成数组后的前缀和一旦出现负数，那么答案必定为 No。考虑如何处理这种情况。

当我们在某次操作时发现 sum<0，便记录其位置（我的代码中是以记录它的位置和当前操作位置的距离来实现的），并标记前缀和有负，答案只能为 No。直到该位置被删除，才解除标记。

显然可以只记录最早的负前缀和（即小于 0 的前缀和）的位置，因为当最前面的负前缀和被删除时，那么它后面的负前缀和肯定也被删除，便不再存在负前缀和了。

提交记录。