zoj 2704 Brackets

zoj 2704 Brackets

/*
此题用cin cout TLE了n次
后来基本上原封不动用了一下C的输入输出方式
结果一次AC
可见C++输入输出方式之慢。。。
此题用了一种比较简便的做法
就是用一个sub[]记录匹配成功的序列
然后从中查找最长的序列
然后输出对应的字符串序列即可 
用此种方法处理的一个很好的优点就是 
可以很好的处理形如[()()][]的序列 
而且不用考虑最长序列在主串的哪个位置 
*/
#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#define N 100005
using namespace std;
char str[N];
int match(int a,int b)
{if((str[a]=='['&&str[b]==']')||(str[a]=='('&&str[b]==')')) return 1;return 0;}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif
 
      int sub[N],len,i,j,l,start,end;
      while(gets(str))
      {
             stack<int> s;
             len=strlen(str);
             memset(sub,0,sizeof(sub));
             s.push(0);
             for(i=1;i<len;i++)//序号入栈 
             {
                      if(s.empty()) s.push(i);
                      else if(match(s.top(),i)){sub[s.top()]=1;sub[i]=1;s.pop();}
                      else s.push(i);                  
             }
             i=start=end=l=0;
             while(i<len)//查找最长的1的序列 
             {
                    j=0;
                    while(i<len&&sub[i]==0) i++;j=i;
                    while(i<len&&sub[i]) i++;
                    if(i-j>l){l=i-j;start=j;end=i;}            
             }//输出 
             for(i=start;i<end;i++)putchar(str[i]);printf("\n\n");
             getchar();//接受实例间的空行    
      }
      return 0;
}

发表回复