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)都会TLE

Posted by jesse_luzexi at 2008-03-27 14:56:47 on Problem 3367
```#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: