[Acwing] 第54场周赛 4430.括号序列

前言

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