A.括号序列
-
一看,我趣,字符串,直接抱灵吧,让我死得体面一点……
-
再一看数据范围,我趣,\(\mathtt{O(n)}\),这怎么写得出来啊?
Solution
-
虽然是 \(\mathtt{O(7n)}\),但卡卡常也就卡过了;
-
先遍历一遍,把括号两两匹配一下,记录一下另一半括号的位置。再来两边 \(\mathtt{O(n)}\),处理出可以形如 \(\mathtt{()()}\) 这样合并的括号个数的前缀和(\(sum_0\))与后缀和(\(sum_1\));
-
然后一遍 \(\mathtt{O(n)}\),统计上面这种方式合并每个位置的答案(为 \((sum_{0,i}-1)\times(sum_{1,pos_i}+1)\))。
-
考虑如何处理括号套括号的情况。