t
a
g
:
tag :
tag: 括号序列 思维 难 传送门 :
题意 : 给定一个括号序列,询问有多少个合法位置,使得修改之后任然满足条件
条件 :
-
s
s
s中的
(和)数量相同 - 对于
s
s
s的任意前缀字符串,其中包含的
(的数量均不少于)的数量
思路 :
考虑操作的只有两种 :
- 将
(改为), R = L + 2 R=L+2 R=L+2 - 将
)改为(, L = R + 2 L=R+2 L=R+2
L , R 指 的 是 字 符 串 中 左 右 括 号 的 数 量 L,R指的是字符串中左右括号的数量 L,R指的是字符串中左右括号的数量
我们考虑第一种操作 :
我们认为(是向上的,)是向下的
因为我们需要满足第二个条件
所以当 y < 0 y
