博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces VK Cup 2015 A.And Yet Another Bracket Sequence(后缀数组+平衡树+字符串)
阅读量:5854 次
发布时间:2019-06-19

本文共 2592 字,大约阅读时间需要 8 分钟。

这题做得比较复杂。。应该有更好的做法

题目大意:

有一个括号序列,可以对其进行两种操作:

·        向里面加一个括号,可以在开头,在结尾,在两个括号之间加。

·        对当前括号序列进行循环移动,即把最后一个括号拿到开头来。

上述两种操作可以做任意次,要求添加最少的括号使得原序列变成一个合法括号序列。如果有多种可能,输出字典序最小的那一个。"(" < ")"。

 

题解:

首先计算左括号和右括号的数量,可以知道,不妨假设左括号的数量大于右括号

那么最少的方案就是在字符串右侧补充右括号,使得左括号的数量等于右括号的数量。

但是一个方案是否可行,要使得前面的每个前缀,都满足条件左括号的数量大于右括号

如果不满足,就循环移动即可,通过循环移动就一定会找到一个方案。

要输出字典序最小的方案,就需要后缀数组了

把字符串循环复制一遍,做后缀数组,那么就知道每个方案的排名

找最小且可行的方案输出即可。

另一种情况是左括号的数量小于右括号,也是同理的。

 

关于如何判断是否可行,这里是用的平衡树

写出每个位置的条件,每移动一次,对所有的条件影响都是相同的,所以用平衡树维护这些条件即可

#include 
#include
#include
#include
#include
#include
using namespace std;const int maxn = 2e6 + 1000;int Wa[maxn], Wb[maxn], Wv[maxn], Ws[maxn], sa[maxn];int Rank[maxn];int height[maxn];set
S;map
M;vector
V;int a[maxn];int cmp(int *r, int a, int b, int l){ return r[a]==r[b] && r[a+l]==r[b+l];}void get_sa(int *r, int *sa, int n, int m){ int i,j,p,*x=Wa,*y=Wb,*t; for(i=0; i
=0; i--) sa[--Ws[x[i]]]=i; for(p=1,j=1; p
=j) y[p++]=sa[i]-j; for(i=0; i
=0; i--) sa[--Ws[Wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i
>str; int n = strlen(str), nl = 0, nr = 0; for(int i = 0; i < n; i++){ if(str[i] == '(') nl++, str[i] = 1; else nr++, str[i] = 2; } if(nl < nr){ tl = 0; for(int i = n-1; i >= 0; i--){ if(str[i] == 1) tl++; a[i] = 2*tl-(n-i); Hinsert(-a[i]); } tl = 0; for(int i = n-1; i >= 0; i--){ if(-(*S.begin()) <= -(n-i-1)+2*tl) V.push_back(i); Herase(-a[i]); if(str[i] == 1) tl++; Hinsert(-(2*nl-n-(n-i)+2*tl)); } int N = 2*n-1; for(int i = 0; i < n; i++) a[i] = str[i]; for(int i = n; i < N; i++) a[i] = str[i-n]; get_sa(a, sa, N+1, 4); for(int i = 1; i <= N; i++) Rank[sa[i]] = i; int maxr = N+100, Kr = 0; for(auto i : V){ if(i+1 >= N) break; if(Rank[i+1] < maxr){ maxr = Rank[i+1]; Kr = i+1; } } a[N] = a[N-n]; for(int i = 0; i < nr-nl; i++) printf("("); for(int i = Kr; i < Kr+n; i++) printf("%c", a[i] == 2 ? ')' : '('); } else { tr = 0; for(int i = 0; i < n; i++){ if(str[i] == 2) tr++; a[i] = 2*tr-i-1; Hinsert(-a[i]); } tr = 0; for(int i = 0; i < n; i++){ if(-(*S.begin()) <= -i+2*tr) V.push_back(i); Herase(-a[i]); if(str[i] == 2) tr++; Hinsert(-(2*nr-n-i-1+2*tr)); } int N = 2*n-1; for(int i = 0; i < n; i++) a[i] = str[i]; for(int i = n; i < N; i++) a[i] = str[i-n]; get_sa(a, sa, N+1, 4); for(int i = 1; i <= N; i++) Rank[sa[i]] = i; int maxr = N+100, Kr = 0; for(auto i : V){ if(Rank[i] < maxr){ maxr = Rank[i]; Kr = i; } } for(int i = Kr; i < Kr+n; i++) printf("%c", a[i] == 2 ? ')' : '('); for(int i = 0; i < nl-nr; i++) printf(")"); }}

 

转载于:https://www.cnblogs.com/Saurus/p/7591531.html

你可能感兴趣的文章
从零开始Docker化你的Node.js应用
查看>>
你真的需要活动目录吗?
查看>>
【Linux系统】模拟MBR扇区故障与恢复 (转)
查看>>
Python自动化开发学习1-2
查看>>
centos6.5下搭建fastdfs分布式存储
查看>>
jdk源码之ConCurrentHashMap源码注释
查看>>
在 PowerPC 下安装 K8S
查看>>
笔记_网络单位换算
查看>>
SCDPM2012 R2实战一:基于SQL 2008 R2集群的SCDPM2012 R2的安装
查看>>
tomcat7 的server.xml 里面 Connector 配置官方说明
查看>>
安装Ruby2.0
查看>>
SQL SERVER中字段类型与C#数据类型的对应关系
查看>>
StringBuffer
查看>>
2017年6月8日 笔记
查看>>
vue.js component 学习手记
查看>>
保存对象、关系映射
查看>>
父页面与子页面的相互操作
查看>>
LVS_DR
查看>>
我的友情链接
查看>>
Java堆和栈的区别
查看>>