csuoj 1809 Parenthesis

csuoj 1809 Parenthesis

第十二届湖南省省赛G题。

//在那之前我还以为签到题是不涉及算法或者数据结构的

Description

1 p 2…p n

ai and p bi

Parenthesis sequence S is balanced if and only if:

S is empty;

or there exists  balanced parenthesis sequence A,B such that S=AB;

or there exists  balanced parenthesis sequence S' such that S=(S').

Input

The input contains at most 30 sets. For each set:

5,1≤q≤10 5).

1 p 2…p n.

i,b i (1≤a i,b i≤n,a i≠b i).

Output

For each question, output " Yes" if P remains balanced, or " No" otherwise.

Sample Input

4 2(())1 32 32 1()1 2

Sample Output

NoYesNo

因为是道括号匹配题，所以可以先用“（”代表1   “ ）”代表-1来求前缀和试试水，0表示这之前的匹配完了。所以前缀和不可能出现-1。

然后写数据找规律，这里写三组

1.（（）） 前缀和为1210 换2 3后前缀和变成1010是yes的

2.（（）（））（）  前缀和为12121010 换2 4后变成1 0 -1 0 1 0是no   换2 3后变成 1 0 1 2 1 0 1 0是yes

3.（（））（） 前缀和为1 2 1 0 1 0 换3 5 或者4 5都是yes的

可以再多列几组，找规律不嫌数据少

可以先预处理一下 比如换一样的括号都是yes

左边是）右边是（的情况一定是yes

涉及到换第一个和最后一个括号一定是no（换的括号不一样）

在上面的数据发现输入x-y的范围内变换之后x-（y-1）的前缀和都变了，都是同时减少了2，这都是和括号变换了之后关系被打乱导致前缀和变了。

如果前缀和减2之后小于0那么变换后的串必不能匹配成功，那么我们只需要知道x-（y-1）的 每个点的前缀和是否大于等于2

即最小值是否大于等于2，要存放前缀和数组并且能够遍历给定的范围并且用时少，这里就要线段树。

每个节点存放最小值，遍历查询最小值。

代码如下：

#include#include#include#includeusing namespace std;#define N 10010000#define INF 0xfffffffchar a[N];int pre[N],tree[N],x,y;void build(int l,int r,int t){ if(l==r){ tree[t]=pre[l-1]; return ; } int mid=(l+r)/2; build(l,mid,t*2); build(mid+1,r,t*2+1); tree[t]=min(tree[t*2],tree[t*2+1]);}int query(int l,int r,int t){ int ans=INF; if(x<=l&&r<=y){ return tree[t]; } int mid=(l+r)/2; if(x<=mid) ans=min(ans,query(l,mid,t*2)); if(y>mid) ans=min(ans,query(mid+1,r,t*2+1)); return ans;}int main(){ int i,j,n,m; while(scanf("%d %d",&n,&m)!=EOF){ cin>>a; memset(pre,0,sizeof(pre)); for(i=0;i>x>>y; if(x>y){ int t=x; x=y;y=t; } if(a[x-1]==a[y-1]||a[x-1]==')'&&a[y-1]=='('){ cout<<"Yes"<=2) cout<<"Yes"<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。