题解 P1944 【最长括号匹配_NOI导刊2009提高（1）】

· · 题解

话说为什么这题是提高+/省选

真是一道水积分的好题~~~

我们直接一个一个压进栈里,把匹配的都弹出去,然后记vis数组vis[i]表示i位是不是成功匹配了

然后找vis数组中最长的一段vis[i]=1的直接输出就好了

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define siz 1000100
using namespace std;
int la,top,cnt,l,ansl,ansr,ans;
int sta[siz][2];
char a[siz];
bool vis[siz];
int main(){

    scanf("%s",a);
    la=strlen(a);
    for(int i=0;i<la;++i) 
      if((sta[top][0]=='['&&a[i]==']')||(sta[top][0]=='('&&a[i]==')')) vis[sta[top--][1]]=vis[i]=1;
      else sta[++top][0]=a[i],sta[top][1]=i;
    for(int i=0;i<la;++i)
      if(!vis[i]) cnt=0,l=i+1;
      else {
          cnt++;
          if(cnt>ans) ansl=l,ansr=i,ans=cnt;
      }
    for(int i=ansl;i<=ansr;++i) putchar(a[i]);
    return 0;
}
O(n)过