首页 > 代码库 > 2016年省赛G题， Parenthesis
2016年省赛G题， Parenthesis
Problem G: Parenthesis
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 398 Solved: 75
[Submit][Status][Web Board]
Description
Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n and q questions.
The i-th question is whether P remains balanced after pai and pbi swapped. Note that questions are individual so that they have no affect on others.
Parenthesis sequence S is balanced if and only if:
1. S is empty;
2. or there exists balanced parenthesis sequence A,B such that S=AB;
3. or there exists balanced parenthesis sequence S‘ such that S=(S‘).
Input
The input contains at most 30 sets. For each set:
The first line contains two integers n,q (2≤n≤105,1≤q≤105).
The second line contains n characters p1 p2…pn.
The i-th of the last q lines contains 2 integers ai,bi (1≤ai,bi≤n,ai≠bi).
Output
For each question, output "Yes" if P remains balanced, or "No" otherwise.
Sample Input
4 2(())1 32 32 1()1 2Sample Output
NoYesNo
比赛的时候，老O查个单词，我后来又查了一下，单词没看完意思，说是"不规则的"，发现里面还有一个括号的意思，也就是说只有括号，当时还以为有其他字符，想了好久，好像其他字符在这里没有起到作用
然后是第二个条件，可不可以反推，纠结了好久，最后还是直接模拟了一遍，虽然已经知道会tle，还是写了一下，当时只有这个题目A得人比较多一点。
解题报告：
1、只有括号
2、3个条件就是括号匹配的实质。
思路：
直接栈模拟是肯定不行的，就算要用栈模拟也不是普通的栈模拟，直接记录左括号的个数，这样模拟。然后这里询问次数10^5，n = 10^5，就是10^10了，这里用线段树优化，每次)(区间都是+2,
直接yes,要是()，就看-2是否是小于0.
#include <stdio.h>#include <algorithm>using namespace std;int temp[100005];char str[100005];#define INF 0x3f3f3f3fstruct node{ int left,right,val;} c[100005*4];void build_tree(int l,int r,int root){ c[root].left=l; c[root].right=r; if(l==r) { c[root].val=temp[l]; return ; } int mid=(l+r)/2; build_tree(l,mid,root*2); build_tree(mid+1,r,root*2+1); c[root].val=min(c[root*2].val,c[root*2+1].val);}void query(int l,int r,int &min1,int root){ if(c[root].left==l&&c[root].right==r) { min1=c[root].val; return ; } int mid=(c[root].left+c[root].right)/2; if(mid<l) query(l,r,min1,root*2+1); else if(mid>=r) query(l,r,min1,root*2); else { int min2; query(l,mid,min1,root*2); query(mid+1,r,min2,root*2+1); min1=min(min1,min2); }}int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { scanf("%s",str+1); int counts = 0; for(int i=1; i<=n; i++) { if(str[i]==‘(‘) temp[i] = ++counts; else temp[i] = --counts; } build_tree(1,n,1); int ls,rs; for(int i=0; i<m; i++) { scanf("%d%d",&ls,&rs); if(ls > rs) swap(ls,rs); if(str[ls]==‘)‘&&str[rs]==‘(‘) { puts("Yes"); continue; } if(str[ls]==str[rs]) { puts("Yes"); continue; } if(str[ls]==‘(‘&&str[rs]==‘)‘) { int mins = INF; query(ls,rs-1,mins,1); if(mins<2) puts("No"); else puts("Yes"); continue; } } } return 0;}
2016年省赛G题， Parenthesis
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。