Open ManuShi98 opened 1 year ago
https://manushi98.github.io/2018/07/04/CodeForces%20Gym%20-%20100803G%20Flipping%20Parentheses(%E7%BA%BF%E6%AE%B5%E6%A0%91)/
思路题意是给定一个匹配好的括号序列，后面有Q次操作，每次操作将第q位的括号反转，你需要找到一个位置反转该位置上的括号让它重新匹配。位置要求是所有可行位置中最左边的。我们令左括号为1，右括号为-1，并求出前缀和。考虑将右括号变为左括号的过程，我们能发现该操作的影响是从该位置到序列尾部的前缀和加2。将左括号变为右括号则是区间-2。为了反转后的括号序列是合法的，我们的前缀和中不能出现小于0的数。因而对操
https://manushi98.github.io/2018/07/04/CodeForces%20Gym%20-%20100803G%20Flipping%20Parentheses(%E7%BA%BF%E6%AE%B5%E6%A0%91)/
思路题意是给定一个匹配好的括号序列，后面有Q次操作，每次操作将第q位的括号反转，你需要找到一个位置反转该位置上的括号让它重新匹配。位置要求是所有可行位置中最左边的。我们令左括号为1，右括号为-1，并求出前缀和。考虑将右括号变为左括号的过程，我们能发现该操作的影响是从该位置到序列尾部的前缀和加2。将左括号变为右括号则是区间-2。为了反转后的括号序列是合法的，我们的前缀和中不能出现小于0的数。因而对操