Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## O(n) + 大量stl = 125ms

Posted by wywcgs at 2008-03-27 15:04:53 on Problem 3367
In Reply To:我说这题是不是有问题？O(n)都会TLE Posted by:jesse_luzexi at 2008-03-27 14:56:47
```> #include "iostream"
> #include "string"
> #include "vector"
> #include "deque"
>
> using namespace std;
>
> struct node
> {
> 	int l;
> 	int r;
> 	int sign;
> 	char c;
> }re[10001];
>
>
> char str[10001];
>
> int main()
> {
> 	int Case;
>
> 	scanf("%d",&Case);
>
> 	for( ; Case-- ; )
> 	{
>
>
> 		scanf("%s",str);
>
> 		deque<node> s;
> 		deque<node> que;
>
> 		s.clear();
> 		int len = strlen(str);
> 		int i,j,k;
> 		node root;
> 		node p;
>
> 		for( i=0 ; i<len ; i++ )
> 		{
> 			//re[i].c = str[i];
> 			//re[i].l = -1;
> 			//re[i].r = -1;
>
> 			if( str[i]>='a'&&str[i]<='z' )
> 			{
> 				node tmp;
> 				tmp.c = str[i];
> 				tmp.l = -1;
> 				tmp.r = -1;
> 				tmp.sign = i;
> 				s.push_back(tmp);
> 				re[i] = tmp;
> 			}
> 			else
> 			{
> 				node tmp;
> 				p.c = str[i];
> 				p.sign = i;
>
> 				tmp = s.back();
> 				s.pop_back();
> 				p.l = tmp.sign;
>
> 				tmp = s.back();
> 				s.pop_back();
> 				p.r = tmp.sign;
>
> 				s.push_back( p );
> 				root = p;
>
> 				re[i] = p;
> 			}
>
> 		}
>
> 		que.clear();
>
> 		que.push_back( root );
>
> 		string res = "";
> 		//res.clear();
> 		node t;
>
> 		//memset(flag,0,sizeof(flag));
>
> 		for( ; !que.empty() ; )
> 		{
> 			t = que.front();
> 			res = t.c + res;
> 			que.pop_front();
>
> 			if( t.r != -1 )
> 			{
> 				que.push_back( re[ t.r ] );
> 			}
>
> 			if( t.l != -1 )
> 			{
> 				que.push_back( re[ t.l ] );
> 			}
>
> 		}
>
> 		printf("%s\n",res.c_str());
>
> 	}
> }
```

Followed by: