CodeForces 1556C Compressed Bracket Sequence

pufanyi

题解

发布于：Aug 31, 2021

给一个长度为 $n\,(1\le n\le 1000)$ 的正整数序列 $\left\{c_n\right\}\,(1\le c_i\le 10^9)$ 。用该序列一如下方式构造一个括号序列 $s$ ：

开始 $c$ 为空；
对 $i$ 从 $1$ 到 $n$ 依次遍历，若 $i$ 为奇数，则在 $s$ 后插入 $c_i$ 个 '('，否则插入 $c_i$ 个 ')'。

求有多少对 $\left<l,r\right>$ 使得 $s_{l\sim r}$ 为合法括号序列。

整一个 $\mathcal{O}(n)$ 的题解吧。

我们分两种情况考虑合法的括号序列：

去掉最左边的 '(' 和最右边的 ')' 仍是合法括号序列的字符串（假设空串也合法），比如 (()()((())))；
去掉最左边的 '(' 和最右边的 ')' 不是合法括号序列的字符串，比如 ()((())())。

我们可以定义第一种括号序列是“独立的”，也就是说她不能被分裂成两个合法括号串；而第二种括号序列是“不独立的”，也就是说，她能被分裂成两个合法的括号串。

我们考虑把两种字符串分开考虑。很显然，每个 ')'，只能作为一个独立括号串的右端点，所以我们统计这部分是非常容易的：跑一遍栈，和平时一样，只是批量地压栈和弹栈，记录弹出的 '(' 次数，即是这部分的答案。

对于非独立的情况，我们考虑在计算独立串的时候同时统计他们，不难发现在对于一个独立串，将此串作为真后缀的非独立串个数即使他左边的连续独立串个数即可，并且我们只要发现出现 )( 的时候才会有非独立串出现，我们考虑在栈中加标记，记录一下出现 )( 的时候其左边连续独立串的个数即可。

具体实现的话，我们开一个栈，栈中压入 pair， $\left<x,1\right>$ 表示有 $x$ 个连续的 '('， $\left<x,0\right>$ 表示这里出现了一个 )(，这个 )( 左边还有几个连续的独立串。压入就直接压连续的 '(' 即可，而弹栈的时候遇到 $\left<x,1\right>$ ，就统计独立串，遇到 $\left<x,0\right>$ 就统计一下非独立串。

考虑到大部分选手应该都不是很熟悉 python，窝把代码做了尽量详细的注释，应该差不多能看懂了 qaq。

n = int(input())
aa = list(map(int, input().split())) # 读入数组 
ans = 0
stk = [] # 栈 
for i in range(n): # [0, n)
  if not stk: # 栈非空 
    stk.append([0, 1]) # push
  if i & 1:
    while aa[i] and stk:
      if stk[-1][1] == 0:
        stk.pop()
      if stk:
        now = stk.pop()
        sub = min(now[0], aa[i])
        aa[i] -= sub
        now[0] -= sub
        ans += sub
        if now[0]:
          stk.append(now)
        if stk and stk[-1][1] == 0:
          ans += stk[-1][0]
    if aa[i]:
      stk.append([0, 1])
    else:
      if not stk:
        stk.append([0, 0])
      if stk[-1][1] == 0:
        stk[-1][0] += 1
      else:
        stk.append([1, 0])
  else:
    if stk[-1][1] == 0:
      stk.append([0, 1])
    stk[-1][0] += aa[i]
print(ans)