精华内容
下载资源
问答
  • 分析:区间dp,装填方程:...不知道为什么voj上gets读取字符串会编译错误,改成fgets就对了。 AC代码: #include #include #include #include using namespace std; const int maxn=100+10; int dp[maxn][maxn]; char

    分析:区间dp,装填方程:dp(i,j)=min(dp(i,k)+dp(k+1,j)) 其中(i<=k<j)  dp(i,j)表示从第i个字符到第j个字符的最小需要添加括号字符的个数,最后递归打印出字符即可。

    不知道为什么voj上用gets读取字符串会编译错误,改成fgets就对了。

    AC代码:

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    using namespace std;
    const int maxn=100+10;
    int dp[maxn][maxn];
    char s[maxn];
    bool match(int i,int j){
    	if(s[i]=='(' && s[j]==')')return true;
    	if(s[i]=='[' && s[j]==']')return true;
    	return false ; 
    }
    
    void print(int i,int j){
    	if(i>j)return ;
    	if(i==j){
    		if(s[i]=='(' || s[i]==')')printf("()");
    		else if(s[i]=='[' || s[j]==']')printf("[]");
    		return ;
    	}
    	
    	if(dp[i][j]==dp[i+1][j-1] && match(i,j)){
    		printf("%c",s[i]);
    		print(i+1,j-1);
    		printf("%c",s[j]);
    		return ;
    	}
    	
    	for(int k=i;k<j;k++){
    		if(dp[i][j]==dp[i][k]+dp[k+1][j]){
    			print(i,k);
    			print(k+1,j);
    			break;
    		}
    	}
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	getchar();  //吃掉换行
    	while(T--){
    		getchar();  //吃掉换行
    	    //gets(s+1);
    	    fgets(s+1,maxn,stdin);
    		int l=strlen(s+1);
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=l;i++)
    	 dp[i][i]=1;
    	 
    	 for(int len=2;len<=l;len++)   //长度 
    	  for(int i=1;i<=l-len+1;i++){   //起点 
    	  	int j=i+len-1;   //终点 
    	  	dp[i][j]=maxn;
    	  	if(match(i,j))dp[i][j]=dp[i+1][j-1];
    	  	else dp[i][j]=dp[i][j-1]+1;
    	  	
    	  	for(int k=i;k<j;k++)
    	  	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
    	  }
    	  
    	  print(1,l);
    	  printf("\n");
    	  if(T)printf("\n");
    //	  printf("%d\n",dp[1][l]);
    	}
    	return 0;
    }









    展开全文
  • 废话不多说,直接上题: ... 这道题一看就会想到区间动态规划(不会戳这里临时补一补),最开始先老老实实地写了一遍区间动态规划,后来觉得栈也可以,于是写了一遍,代码如下: 1 #include<iostrea...

      废话不多说,直接上题:


      题目测评链接:戳这里

      其实什么GBE都没用,小编最开始看了半天不懂,看了看别人的博客才知道这段话没什么用处。其实就是给一段字符串,判断是否括号是配对的。

      这道题一看就会想到区间动态规划(不会戳这里临时补一补),最开始先老老实实地写了一遍区间动态规划,后来觉得用栈也可以,于是写了一遍,代码如下:

     1 #include<iostream>
     2 #include<cstring>
     3 #include<stack>
     4 using namespace std;
     5 string s;int n,wrong;
     6 stack<int>a;
     7 int main()
     8 {
     9     cin>>s;
    10     n=s.length();
    11     for(int i=0;i<n;i++)
    12     {
    13         if(s[i]=='(') a.push(1);
    14         else if(s[i]==')') 
    15         {
    16             if(!a.empty())
    17             {
    18                 if(a.top()==1) a.pop();
    19                 else wrong++;
    20             }
    21             else wrong++;
    22         }
    23         else if(s[i]=='[') a.push(2);
    24         else if(s[i]==']') 
    25         {
    26             if(!a.empty())
    27             {
    28                 if(a.top()==2) a.pop();
    29                 else wrong++;
    30             }
    31             else wrong++;
    32         }
    33     }
    34     cout<<wrong;
    35     return 0;
    36 }

      想法很简单,检测到或 时,就判断是否能配对,如果不行,就记录下这个错误。

      样例很快就过了,但是测评时错了4个测试点,检查了一下,才发现了一些bug,比如输入([)]期望得到4,而只得到了1。所以还是老老实实用区间动态规划吧。

      首先思考一个问题:需要补上的括号数=没有成功配对的括号数=总括号数-能正确配对的括号数。

      所以,我们不妨这样设计状态:用f[i][j]表示ij区间内能配对成功的括号数。

      那么f[i][j]怎么转移呢?如果用s数组来表示字符串,那么如果s[i]==s[j],那么就有f[i][j]=f[i+1][j-1]+2。可能有点难理解,图解一下:

      

      那么这是s[i]==s[j]时的操作(难点),剩下的就是老套路了,f[i][j]=max(f[i][j],f[i][k]+f[k+1][j])

      代码很简单,就不加注释了。

     1 #include<iostream>
     2 #include<cstring>
     3 using namespace std;
     4 string s;int n,f[1000][1000];
     5 int main()
     6 {
     7     cin>>s;
     8     n=s.length();
     9     for(int t=1;t<=n-1;t++)
    10     for(int i=0;i<n-t;i++)
    11     {
    12         int j=i+t;
    13         if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) f[i][j]=f[i+1][j-1]+2;
    14         for(int k=i;k<j;k++)
    15         f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
    16     }
    17     cout<<n-f[0][n-1];
    18     return 0;
    19 }

    转载于:https://www.cnblogs.com/TFLS-gzr/p/11169538.html

    展开全文
  • HNOI2011 括号修复

    2019-10-05 00:20:41
    题目描述 题解: 首先,任意一个括号序列消去成对括号后一定是‘)))……)(……(((’的形式。 如果我们能求出当前子序列消去后剩下的东西长什么样,我们就能O...splay支持区间翻转,考虑splay维护。 这里引入我...

    题目描述

    题解:

    首先,任意一个括号序列消去成对括号后一定是‘)))……)(……(((’的形式。

    如果我们能求出当前子序列消去后剩下的东西长什么样,我们就能O(1)出解。

    比如前面有a个')',后面有b个‘(’。

    那么$ans = (a+1)/2 + (b+1)/2$.

    建议自己画一画。

    现在的问题是怎么修改。

    splay支持区间翻转,考虑用splay维护。

    这里引入我的构造想法,不知道有没有人用:

    将')''('分别作为:

    这样串$))(((((())))$可表示为:

    我们可以发现,剩余的')'就是正向看的最大向上高度,'('就是反向看的最大向下高度

    所以我们要维护这两个值。

    这样replace和swap操作可以解决。

    那么invert呢?

    就是让这个图形上下倒过来画咯。

    所以我们还要维护最小向上/向下高度。

    所以总结一下:

    swap:交换两个最大、交换两个最小;

    invert:交换两个正向看的值并变成相反数、交换两个反向看的值并变成相反数;

    replace:区间赋值,重要的是清invert标记!!!

    然后代码:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define N 100050
    int n,m;
    char s[N];
    struct Splay
    {
        int fa[N],ch[N][2],siz[N],rt,rep[N];
        bool swa[N],inr[N];
        int v[N],f[N][2],g[N][2],tag[N],sum[N];//max/min front max/min back
        void update(int u)
        {
            int ls = ch[u][0],rs = ch[u][1];
            siz[u] = siz[ls]+siz[rs]+1;
            sum[u] = sum[ls]+sum[rs]+v[u];
            f[u][0] = max(f[ls][0],sum[ls]+v[u]+f[rs][0]);
            f[u][1] = min(f[ls][1],sum[ls]+v[u]+f[rs][1]);
            g[u][0] = max(g[rs][0],sum[rs]+v[u]+g[ls][0]);
            g[u][1] = min(g[rs][1],sum[rs]+v[u]+g[ls][1]);
        }
        void Swap(int u)
        {
            if(!u)return ;
            swa[u]^=1;
            swap(ch[u][0],ch[u][1]);
            swap(f[u][0],g[u][0]);
            swap(f[u][1],g[u][1]);
        }
        void Inr(int u)
        {
            if(!u)return ;
            inr[u]^=1;
            v[u]=-v[u];sum[u]=-sum[u];
            swap(f[u][0],f[u][1]);
            swap(g[u][0],g[u][1]);
            f[u][0]=-f[u][0];f[u][1]=-f[u][1];
            g[u][0]=-g[u][0];g[u][1]=-g[u][1];
        }
        void Rep(int u,int d)
        {
            if(!u)return ;
            tag[u]=d;
            inr[u]=0;
            v[u]=d;
            if(d==1)
            {
                sum[u]=siz[u];
                f[u][0]=g[u][0]=siz[u];
                f[u][1]=g[u][1]=0;
            }else
            {
                sum[u]=-siz[u];
                f[u][0]=g[u][0]=0;
                f[u][1]=g[u][1]=-siz[u];
            }
        }
        void pushdown(int u)
        {
            int ls = ch[u][0],rs = ch[u][1];
            if(tag[u])
            {
                Rep(ls,tag[u]),Rep(rs,tag[u]);
                tag[u]=0;swa[u]=0;
            }
            if(swa[u])
            {
                Swap(ls),Swap(rs);
                swa[u]=0;
            }
            if(inr[u])
            {
                Inr(ls),Inr(rs);
                inr[u]=0;
            }
        }
        int st[N],tl;
        void down(int u)
        {
            tl=0;st[++tl]=u;
            while(fa[u])u=fa[u],st[++tl]=u;
            while(tl)pushdown(st[tl]),tl--;
        }
        void rotate(int x)
        {
            int y = fa[x],z = fa[y],k = (ch[y][1]==x);
            ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y;
            ch[x][!k]=y,fa[y]=x;
            ch[z][ch[z][1]==y]=x,fa[x]=z;
            update(y),update(x);
        }
        void splay(int x,int goal)
        {
            down(x);
            while(fa[x]!=goal)
            {
                int y = fa[x],z = fa[y];
                if(z!=goal)
                    (ch[z][1]==y)^(ch[y][1]==x)?rotate(x):rotate(y);
                rotate(x);
            }
            if(!goal)rt = x;
        }
        int get_pnt(int x,int k)
        {
            pushdown(x);
            int tmp = siz[ch[x][0]];
            if(k<=tmp)return get_pnt(ch[x][0],k);
            else if(k==tmp+1)return x;
            return get_pnt(ch[x][1],k-tmp-1);
        }
        int build(int l,int r,int f)
        {
            if(l>r)return 0;
            int x = (l+r)>>1;
            fa[x] = f;
            v[x] = (s[x]=='('?-1:1);
            ch[x][0] = build(l,x-1,x);
            ch[x][1] = build(x+1,r,x);
            update(x);
            return x;
        }
        void split(int &x,int &y)
        {
            x = get_pnt(rt,x);
            y = get_pnt(rt,y+2);
            splay(x,0);splay(y,x);
        }
        void _replace(int x,int y,int d)
        {
            split(x,y);
            Rep(ch[y][0],d);
            update(y),update(x);
        }
        void _swap(int x,int y)
        {
            split(x,y);
            Swap(ch[y][0]);
            update(y),update(x);
        }
        void _invert(int x,int y)
        {
            split(x,y);
            Inr(ch[y][0]);
            update(y),update(x);
        }
        int _query(int x,int y)
        {
            split(x,y);
            return (f[ch[y][0]][0]+1)/2+(-g[ch[y][0]][1]+1)/2;
        }
    }tr;
    char opt[20];
    int main()
    {
        scanf("%d%d%s",&n,&m,s+2);
        tr.rt=tr.build(1,n+2,0);
        for(int x,y,i=1;i<=m;i++)
        {
            scanf("%s%d%d",opt+1,&x,&y);
            if(opt[1]=='R')
            {
                scanf("%s",opt+1);
                int d = 1;
                if(opt[1]=='(')d=-1;
                tr._replace(x,y,d);
            }else if(opt[1]=='S')
            {
                tr._swap(x,y);
            }else if(opt[1]=='I')
            {
                tr._invert(x,y);
            }else
            {
                printf("%d\n",tr._query(x,y));
            }
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/LiGuanlin1124/p/10160510.html

    展开全文
  • 【BZOJ2329】括号修复(Splay) 题面 BZOJ 洛谷 题解 本来想着线段树来写 但是有一个区间翻转 所以不能线段树了,就只能平衡树 然后直接\(Splay\)就好了 注意一下几个标记的下放问题 这种数据结构真的没有...

    【BZOJ2329】括号修复(Splay)

    题面

    BZOJ
    洛谷
    4.jpg

    题解

    本来想着用线段树来写
    但是有一个区间翻转
    所以不能用线段树了,就只能用平衡树
    然后直接\(Splay\)就好了
    注意一下几个标记的下放问题
    这种数据结构真的没有什么思路可言。。

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<set>
    #include<map>
    #include<vector>
    #include<queue>
    using namespace std;
    #define ll long long
    #define RG register
    #define MAX 111111
    #define ls (t[x].ch[0])
    #define rs (t[x].ch[1])
    inline int read()
    {
        RG int x=0,t=1;RG char ch=getchar();
        while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
        if(ch=='-')t=-1,ch=getchar();
        while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
        return x*t;
    }
    struct Node
    {
        int ch[2],ff,size;
        int lm,rm,lg,rg,sum,v;
        int rev,eql,inv;
    }t[MAX];
    int rt;
    void pushup(int x)
    {
        t[x].lm=max(t[ls].lm,t[ls].sum+t[x].v+t[rs].lm);
        t[x].rm=max(t[rs].rm,t[rs].sum+t[x].v+t[ls].rm);
        t[x].lg=min(t[ls].lg,t[ls].sum+t[x].v+t[rs].lg);
        t[x].rg=min(t[rs].rg,t[rs].sum+t[x].v+t[ls].rg);
        t[x].sum=t[ls].sum+t[rs].sum+t[x].v;
        t[x].size=t[ls].size+t[rs].size+1;
    }
    void rotate(int x)
    {
        int y=t[x].ff,z=t[y].ff;
        int k=t[y].ch[1]==x;
        if(z)t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;
        t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;
        t[x].ch[k^1]=y;t[y].ff=x;
        pushup(y);
    }
    void putrev(int x)
    {
        if(!x)return;
        swap(t[x].lg,t[x].rg);
        swap(t[x].lm,t[x].rm);
        swap(ls,rs);t[x].rev^=1;
    }
    void putinv(int x)
    {
        if(!x)return;
        t[x].v*=-1;t[x].inv^=1;t[x].sum*=-1;
        swap(t[x].lm,t[x].lg);swap(t[x].rm,t[x].rg);
        t[x].lm*=-1;t[x].lg*=-1;t[x].rm*=-1;t[x].rg*=-1;
    }
    void puteql(int x,int w)
    {
        if(!x)return;
        t[x].eql=t[x].v=w;t[x].sum=t[x].size*w;
        t[x].rev=t[x].inv=0;
        t[x].lm=t[x].rm=max(0,t[x].sum);
        t[x].lg=t[x].rg=min(0,t[x].sum);
    }
    void pushdown(int x)
    {
        if(t[x].eql)puteql(ls,t[x].eql),puteql(rs,t[x].eql),t[x].eql=0;
        if(t[x].rev)putrev(ls),putrev(rs),t[x].rev^=1;
        if(t[x].inv)putinv(ls),putinv(rs),t[x].inv^=1;
    }
    void Splay(int x,int goal)
    {
        while(t[x].ff!=goal)
        {
            int y=t[x].ff,z=t[y].ff;
            if(z!=goal)
                (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!goal)rt=x;pushup(x);
    }
    int Kth(int x,int k)
    {
        while(233)
        {
            pushdown(x);
            if(k<=t[ls].size)x=ls;
            else if(k==t[ls].size+1)return x;
            else k-=t[ls].size+1,x=rs;
        }
    }
    int split(int l,int r)
    {
        int x=Kth(rt,l);Splay(x,0);
        int y=Kth(rt,r+2);Splay(y,x);
        return t[y].ch[0];
    }
    void Build(int l,int r,int ff)
    {
        if(l>r)return;
        int mid=(l+r)>>1;
        t[mid].ff=ff;
        if(ff)t[ff].ch[ff<mid]=mid;
        else rt=mid;
        Build(l,mid-1,mid);Build(mid+1,r,mid);
        pushup(mid);
    }
    char S[MAX];
    int n,m;
    int main()
    {
        n=read();m=read();
        scanf("%s",S+1);
        for(int i=1;i<=n;++i)t[i+1].v=(S[i]=='('?-1:1);
        Build(1,n+2,0);
        char ch[10];
        while(m--)
        {
            scanf("%s",ch);
            int l=read(),r=read(),x=split(l,r);
            if(ch[0]=='Q')printf("%d\n",(t[x].lm+1)/2+(1-t[x].rg)/2);
            else if(ch[0]=='S')putrev(x);
            else if(ch[0]=='R')
            {
                scanf("%s",ch);int w=(ch[0]=='('?-1:1);
                puteql(x,w);
            }
            else putinv(x);
        }
        return 0;
    }
    

    转载于:https://www.cnblogs.com/cjyyb/p/8809958.html

    展开全文
  • //区间DP 记忆化搜索 //虽然没做过记忆化搜索的题 也不知道什么是记忆化搜索 //但见网上大神们都这样...//dp[i][j][c1][c2]表示i到j区间第i个括号染色为c1,第j个括号染色为c2的所有符合要求的情况数 #include
  • Problem传送门Solution这道题目很显然是类似于区间DP的,但是状态上要记录最旁边两个的颜色,为什么?因为你要判断更外层染什么...2.当最外面不匹配时肯定是多个括号并列,乘法原理计算,我已开始把 int x=match[l]
  • 有两种操作,1翻转某个括号2求只使用指定区间括号,去掉匹配的括号后,第k个括号什么。首先建立一颗线段树,每个节点存储两个值rnum,lnum,代表仅使用这个区间括号,去掉匹配的括号后剩下多少左括号括号...
  • 应该是一个封闭的区间(需要括号将其封装) 需要给这个区间起一个名字(的时候通过这个名字来进行调用) 这个区间需要有参与运算的数据 需要定义该功能的结果类型(返回值类型) public static void draw(int...
  • 一个中括号来实现 为什么没有-0??去清醒脑子想想 -0 和 0 有差吗? 还有一个切片操作 就像切菜那样简单,同样是中括号 接上面那个图 这个中括号有三个参数 [ 开始 : 结束 : 长度] 这三个参数是可以省略的...
  • Brackets sequence

    2020-03-20 21:35:48
    有一串只包含"(",")","[","]“的字符串,例如”([)",现在想要给它补全括号,让它变成正常的括号序列,比如[()],([()]),问最短的序列是什么 解法: 区间dp dp[i][j]dp[i][j]dp[i][j]来表示区间i~j内要补充的最短...
  • 先说一下什么括号序列,就是在$dfs$的时候,进入的时候记录一下,出去的时候也记录一下 拿样例为例,它的括号序列就是$12443321$ 那么我们扩展区间对答案的贡献是可以$O(1)$计算的 假设扩展出的点的颜色是$c$,...
  • 基础知识点 While 和 for 循环以冒号“:” 结尾 For循环 以 in 进行遍历 函数 函数定义以关键字“def”... 文档字符串(“docstring”)三引括号起,以描述函数是做什么的,eg:"""函数作用说明""" ...
  • java学习笔记03

    2015-11-19 18:48:33
    一、第一个小程序 1、class为java语言中的关键字,专门用于定义类; ...关键字:被java语言赋予了特殊含义的单词;...4、主函数,主函数代码范围一对大括号; 主函数保证类的独立运行。主函数的字母什么的写
  • 而且所有涉及区间的都是已经算好的dp值,比如那个折叠的地方,不是直接的长度,而是那一块的dp值! 不需要把dp想复杂。只要考虑设计了状态之后怎样转移。  转移常常需要分类讨论,比如这...
  • (根本不需要用什么树链剖分)。O(NlogN)+常数小,成功用小号刷到rank2。  这道题目其实是可以在线的,C相当于一个颜色,然后把dfs序列改成括号序列(这样就不会有多次修改重复用一个东西了)。使用带修改的主席树...
  • UVa1626

    2019-11-04 18:28:03
    题意 求一个字符串中最少需要补多少括号使得字符串为规则字符串 思路 其实看到了序列或者区间问题,就很容易想到定义d[i][j]为...为什么呢,其实在分为两个区间的时候,我们是要默认两个区间互不干扰的,那么就是...
  • 什么要使用switch循环结构:因为多重if选择结构从代码上看的话,显得结构复杂,容易出错,代码多,冗余且有多次的等值判断。为了解决上述问题,我们...switch语法结构:switch(){ //switch后面的括号里可以ints...
  • Java 小白第三天

    2019-12-06 21:21:50
    适合用于什么场景:用于区间值的判定 可用于固定值的判定 浮点类型的变量不适合if语句判定 Switch case break;语句 适合用于固定值的判定 While语句 括号中是一个布尔类型表达式 结果为true执行false不执行 Do ...
  • Linux正则表达式使用方法详解

    千次阅读 2020-07-29 01:16:49
    正则表达式一、什么是正则表达式1. 定义2. 正则表达式的类型二、 基本正则表达式(BRE模式)1.纯文本2.特殊字符3.锚字符3.1 锁定在行首3.2 ...正则表达式是你所定义的模式模板(pattern template),Linux工具可以
  • PO 3683 2-sat问题

    2019-04-18 19:52:49
    学习一下判断两个区间是否重叠的办法,当且仅当,左端点的最大值小于右端点的最小值的时候,有交集。(具体问题分析取等号的问题) 当然直接向我这样调用函数判断,没有交集的情况也是可以的,不过慢了300ms。。。。...
  • 正则表达式与re模块

    2020-08-04 10:15:49
    区间(二)在python中使用re模块1.python中常的元字符及其含义2.普通匹配示例3.正则匹配示例(1)\w(2)\W(3)\s(4)\S(5)\d(6)\D(7)\n与\t(8)^与$(9). 与[]、中括号内取反、*、+、{n,m}、?、. *、...
  • Linux命令行与shell脚本编程大全(第2版)

    千次下载 热门讨论 2014-02-20 13:51:01
    19.2.7 使用区间 19.2.8 特殊字符组 19.2.9 星号 19.3 扩展正则表达式 19.3.1 问号 19.3.2 加号 19.3.3 使用花括号 19.3.4 管道符号 19.3.5 聚合表达式 19.4 实用中的正则表达式 19.4.1 目录文件计数 ...
  • 我要是只写一个包含 LeetCode 题目代码的仓库,有个锤子?没有思路解释,没有思维框架,顶多写个时间复杂度,那玩意一眼就能看出来。 只想要答案的话很容易,题目评论区五花八门的答案,动不动就秀 python 一行...

空空如也

空空如也

1 2 3
收藏数 48
精华内容 19
关键字:

区间用什么括号