1264D
CF1264D2 Beautiful Bracket Sequence
第二次听这道题,写个推导过程。 考虑对于给定的括号序列如何算答案,考虑最终答案对应回原序列的位置,于是我们要找到一个位置让其左边的左括号与右边的右括号一样多。因为挪指针时两者之一一定变化,并且两边均单调,所以这个分界点是唯一的。 考虑枚举分界点算答案。假设左边有 \(x\) 个问号,右边有 \(y\ ......
[CF1264D]Beautiful Bracket Sequence
题目描述 This is the hard version of this problem. The only difference is the limit of $ n $ - the length of the input string. In this version, $ 1 \leq n ......
CF1264D Beautiful Bracket Sequence
这里是加强版,$n\le 10^6$。 考虑到最后删剩下括号序列形如 `(((...(()))...))`,想到枚举分界点。 设 $p$ 为当前枚举的分界点,$l$ 为 $[1,p]$ 内 `(` 的个数,$r$ 为 $[p+1,n]$ 内 `)` 的个数,$x$ 为 $[1,p]$ 内 `?` 的 ......
题解 CF1264D1
前言 数学符号约定: $\dbinom{n}{m}$:表示 $n$ 选 $m$ 。 如非特殊说明,将会按照上述约定书写符号。 题目分析: 考虑题目的问题弱一点的版本,假设此时我们的括号序列是确定的如何求其括号匹配的最深深度。 如果你有些许 dp 基础的话,不难想到如下做法: 考虑位置 $i$,将区间 ......