首页 > 其他分享 >gym104531 I Bracket

gym104531 I Bracket

时间:2023-09-15 09:36:00浏览次数:43  
标签:gym104531 le forall ge Bracket 序列 sa

题意

题面

做法

结论:对于字符串\(s\),其为合法括号序列的充要条件为
(1)\(|s|\)为偶数,
(2)构造序列\(a_i\),若\(s_i\)='(' or '?',则\(a_i=+1\);若\(s_i\)=')',则\(a_i=-1\),\({a_i}\)的前缀和均\(\ge 0\)
(3)构造序列\(b_i\),若\(s_i=\)')' or '?',则\(b_i=+1\);若\(s_i\)='(',则\(b_i=-1\),\({b_i}\)的后缀和均\(\ge 0\)

证明显然

令\(sa_i,sb_i\)分别为\(\{a\},\{b\}\)的前缀和、后缀和。

推论:\(s_{l,r}\)为合法括号序列的充要条件为
(1)\(r-l+1\)为偶数
(2)\(\forall i\in[l,r]\),\(sa_{l-1}\le sa_i\)
(3)\(\forall i\in[l,r]\),\(sb_{r+1}\le sa_i\)

令\(nxt_i=\min\{x|x>i \and sa_x<sa_i\}\),\(pre_i=\max\{x|x<i \and sb_x<sb_i\}\)

推论(2)(3)可改写为,\(r< nxt_{l-1}\)、\(l> pre_{r+1}\)

令\(f_i\)为前\(s[1:i]\)的最大价值,转移是一个经典的二维偏序问题

标签:gym104531,le,forall,ge,Bracket,序列,sa
From: https://www.cnblogs.com/Grice/p/17703801.html

相关文章

  • 软件测试|好用的pycharm插件推荐(三)——Rainbow Brackets
    简介我们平时写代码的时候,括号是让我们非常头疼的地方,特别是代码逻辑很多,层层嵌套的情况。一眼很难看出,代码是从哪个括号开始,到哪个反括号结束的。这个时候要是有一款工具能够让我们一眼就看出代码从哪个括号开始,到哪个反括号结束,无疑对我们会有很大帮助。PyCharmRainbowBracket......
  • CF670E Correct Bracket Sequence Editor
    思路发现此题除了模拟没有好的方法,所以考虑如何模拟。先考虑删除操作,如果在删除的时候再去找要删除那些的话,就会使时间复杂度变高,所以考虑先预处理出每个括号对应的位置。如果按照操作删除括号,那么时间复杂度也是非常吓人的。所以我们考虑标记被删除的括号。再考虑移动操作,如果......
  • 插件Rainbow Brackets插件使用
    插件RainbowBrackets1.自带花括号彩虹色2.高亮部分代码块command+右键代码块3.着重展示,其余都黑标alt+右键代码块4.取消代码高亮按esc......
  • Vanya and Brackets 题解
    题目传送门一道枚举题。枚举左括号和右括号的位置括号,为了答案最优,左括号只能在开头或者*的右边。右括号只能在末尾或者*的左边。每一次枚举都计算一下这个加了括号后表达式的值,最后取最大值即可。Code#include<bits/stdc++.h>#definelllonglong#defineINF1e9usi......
  • CF1264D Beautiful Bracket Sequence
    这里是加强版,\(n\le10^6\)。考虑到最后删剩下括号序列形如(((...(()))...)),想到枚举分界点。设\(p\)为当前枚举的分界点,\(l\)为\([1,p]\)内(的个数,\(r\)为\([p+1,n]\)内)的个数,\(x\)为\([1,p]\)内?的个数,\(y\)为\([p+1,n]\)内?的个数。那么\(p\)这个......
  • 题解 Bracket Insertion
    BracketInsertion神仙DP题,不愧是tourist。容易发现,括号序列一共有\(1\cdot3\cdot5...\cdot(2n-1)\)种生成方式。假如(为\(1\),)为\(-1\),那么一个序列合法的充要条件为:最小前缀和为\(0\),且以\(0\)结尾。现在考虑维护这些前缀和。如果我们在当前序列某一位后插......
  • 题解 CF1830C【Hyperregular Bracket Strings】
    卡特兰数一个长为\(2n\)的序列,填入括号,有多少种合法方案?\(C_n=\sum_iC_iC_{n-i-1}\),其中\(C_0=C_1=1\)。它的封闭形式是\(C_n=\binom{2n}{n}-\binom{2n}{n-1}\)。problem给定一个长度\(n\)和\(k\)个子区间\(\{[l1​,r1​],[l2​,r2​],…,[lk​,rk​]\}\)。问有多......
  • AtCoder Regular Contest 141 C Bracket and Permutation
    洛谷传送门AtCoder传送门考虑给出\(S\),如何求\(P,Q\)。先考虑\(P\),那我们肯定想让\(P\)的每一项都尽量往前靠。设\([1,k]\)为合法括号串,\(S_{k+1}=\texttt{)}\),那\(P\)的前\(k\)项依次为\(1\simk\),第\(k+1\)项不能为\(k+1\)了,那找到\(k+1\)之......
  • CodeForces 1830C Hyperregular Bracket Strings
    洛谷传送门CF传送门每一步思路都非常自然的题。考虑先从一些简单的case入手。1.\(k=0\)设\(g_i\)为长度为\(i\)的合法括号串数。显然\(\foralli\nmid2,g_i=0\)。对于偶数的\(i\),这是一个经典问题,\(g_i\)就是第\(\frac{i}{2}\)项卡特兰数,因此\(g_i=\bi......
  • P9356 「SiR-1」Bracket 题解
    P9356「SiR-1」Bracket题解首先我们来先考虑一下如何计算一个给定的\(f(s[1,n])\)。一般括号序列的题目都是比较套路的将\(\texttt{(}\)赋值为\(1\),将\(\texttt{)}\)赋值为\(-1\),然后求一下前缀和记为\(sum_i\),那么一个括号序列是合法的当且仅当\(\foralli\in[1,n],......