关于括号序列，有很多有意思的题可以说。最近我就做了许多关于括号序列的题，其中有很简单的，也有很难的。
这篇文章用于记录关于括号序列的一些结论和趣题，不定期更新。
水题：poj3991
给出一个括号序列，问你最少改变几个括号，使得这个括号序列成为合法的括号序列（这里的合法，是指左括号与右括号不一定连续的完全匹配，下面还有一道题和这个要求不同，做法也大相径庭）。
经典水题，我们只需要记录左括号的数量，如果扫描到右括号，就用左边的左括号匹配，如果左面没有左括号匹配了，就把这个右括号变成左括号。
最后，我们剩下的一定是一堆左括号，把这堆左括号中的一半变为右括号即可。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<stack> using namespace std; const int N=2005; char s[N]; int main() { int cnt=0; while(scanf("%s",s+1)!=EOF) { if(s[1]=='-')return 0; int len=strlen(s+1); int l=0,ans=0; for(int i=1;i<=len;i++) { if(s[i]=='{')l++; else { if(l>0)l--; else ans++,l++; } } printf("%d. %d\n",++cnt,ans+l/2); } return 0; }
水题 poj1068
定义P序列为每个右括号左侧的左括号数量，W序列为【在仅计算左括号的情况下，当前右括号与其左侧最近的左括号的距离】。
给出P序列，求W序列。
显然我们根据P序列模拟可以得到这个括号序列，然后再根据这个括号序列模拟得到W序列即可。
得到W序列的过程中我用了栈作为辅助。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<stack> using namespace std; const int N=2005; char s[N]; int a[N],n,sum[N]; int main() { int cnt=0; scanf("%d",&cnt); while(cnt--) { int tot=0; scanf("%d",&n); memset(sum,0,sizeof sum); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=a[1];i++)s[++tot]='('; s[++tot]=')'; for(int i=2;i<=n;i++) { int t=a[i]-a[i-1]; for(int j=0;j<t;j++) s[++tot]='('; s[++tot]=')'; } for(int i=1;i<=tot;i++) { sum[i]=sum[i-1]; if(s[i]==')')sum[i]++; } stack<int>sta; for(int i=1;i<=tot;i++) { if(s[i]==')')printf("%d ",i-(sum[i-1]-sum[sta.top()])-sta.top()),sta.pop(); else sta.push(i); } puts(""); } return 0; }
难题
Gym – 101341 A Streets of Working Lanterns – 2
给出n个括号序列，要求把这n个括号序列进行拼接，形成一个合法的括号序列。
神题。
首先有一个显然错误但是方向比较正确的贪心：先放左括号多的。
但是这样出现一个问题，(((((()))))))))) 这种也算是左括号多的序列，但是中途某个时刻右括号非常多，很容易爆掉，所以这个贪心还需要改进。
我们令左括号为+1，右括号为-1。我们记录两个值，一个是当前括号序列的最终结果l，如果这个结果小于0，那么就令l=0。一个是当前括号序列中途最惨的情况r。
写成如下代码：
for(int j=0;j<len;j++) { if(s[i][j]=='(')a[i].l++; else { if(a[i].l>0)a[i].l--; else a[i].r++; } }
考虑比较函数cmp：
如果比较的两个序列a,b的中途最惨情况都为0，直接比较最终结果谁大就好，这个是一开始的贪心策略。
如果两个序列的中途最惨情况有一个为0，一个不为0，则先放为0的
如果两个序列的中途最惨情况都不为0：
1 如果两个序列的最终结果都是左括号多，那么直接看谁的最惨情况比较小就好了。
2 如果一个序列的最终结果是右括号多，另一个是左括号多，那么显然先选左括号多的。
3 如果两个序列的结果都是右括号多，那么比较两个序列的l值，先放l值大的。
然后就排序就好了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; const int N=200005; struct pos { int l,r; int p; }a[N],b[N]; int c1,c2; bool cmp(pos a,pos b) { if(a.r==0&&b.r==0)return a.l>b.l;//如果都在x轴以上 则先放大的 if(a.r>0&&b.r>0)//最小值都爆了x轴 { if(a.l>a.r&&b.l>b.r)//都是左括号多一些 return a.r<b.r;//把右括号少的先放 if(a.l>a.r)return 1;//先放我 if(b.l>b.r)return 0;//先放我 return a.l>b.l;//这俩都是右括号多 谁左括号多先放谁 } if(a.r==0)return 1; return 0; } string s[N]; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>s[i]; int len=s[i].length(); int now=0,ret=0x3f3f3f3f; for(int j=0;j<len;j++) { if(s[i][j]=='(')a[i].l++; else { if(a[i].l>0)a[i].l--; else a[i].r++; } } a[i].p=i; } sort(a+1,a+n+1,cmp); // for(int i=1;i<=c1;i++)cout<<a[i].m<<" "<<a[i].now<<endl; // for(int i=1;i<=c2;i++)cout<<b[i].m<<" "<<b[i].now<<endl; int ans=0; for(int i=1;i<=n;i++) { int len=s[a[i].p].length(); for(int j=0;j<len;j++) { if(s[a[i].p][j]=='(')ans++; else ans--; if(ans<0) { puts("NO"); return 0; } } } if(ans!=0){puts("NO");return 0;} puts("YES"); for(int i=1;i<=n;i++) printf("%d ",a[i].p); return 0; }
hdu6299 2018多校Balanced Sequence
给出n个括号序列，要求把这些序列拼起来，形成一个新的括号序列，其中能匹配的子序列(可以不连续)最大
实质是求最大匹配。我们先用一个栈把已经匹配上的括号序列删掉，最后会剩下一些序列。
用上面那个题的神级排序函数(其实自己再写一个简单点的也行)，对剩余的括号序列进行排序，一定能得到最大匹配
最后扫一遍即可。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<stack> using namespace std; const int N=100005; string s[N]; int n,ret; struct pos { int l,r; int p; }a[N]; bool cmp(pos a,pos b) { if(a.r==0&&b.r==0)return a.l>b.l; if(a.r>0&&b.r>0) { if(a.l>a.r&&b.l>b.r)return a.r<b.r; if(a.l>a.r)return 1; if(b.l>b.r)return 0; return a.l>b.l; } if(a.r==0)return 1; return 0; } int main() { int cnt=0; std::ios::sync_with_stdio(false); cin>>cnt; while(cnt--) { cin>>n; ret=0; for(int i=1;i<=n;i++) { cin>>s[i]; stack<char>sta; int len=s[i].length(); for(int j=0;j<len;j++) { if(s[i][j]=='(')sta.push(s[i][j]); else if(s[i][j]==')') { if(!sta.empty()&&sta.top()=='(') ret+=2,sta.pop(); else sta.push(s[i][j]); } } s[i].clear(); while(!sta.empty()) s[i]+=sta.top(),sta.pop(); reverse(s[i].begin(),s[i].end()); } for(int i=1;i<=n;i++) { int len=s[i].length(); int l,r;l=r=0; for(int j=0;j<len;j++) { if(s[i][j]=='(')l++; else { if(l>0)l--; else r++; } } a[i].l=l; a[i].r=r; a[i].p=i; } sort(a+1,a+n+1,cmp); int flag=0; for(int i=1;i<=n;i++) { int len=s[a[i].p].length(); for(int j=0;j<len;j++) { if(s[a[i].p][j]==')') { if(flag>0)flag--,ret+=2; } else flag++; } } cout<<ret<<endl; } return 0; }
未完待续…….