poj1068 Parencodings 模拟水题

 1 ///2014.3.8
 2 ///poj1068
 3 
 4 //time:0MS
 5 
 6 /**
 7  *对于给出的原括号串，存在两种数字密码串：
 8  *1.p序列：当出现匹配括号对时，
 9  *  从该括号对的右括号开始往左数，
10  *  直到最前面的左括号数，就是pi的值。
11  *2.w序列：当出现匹配括号对时，
12  *  包含在该括号对中的所有右括号数（包括该括号对）,
13  *  就是wi的值。
14  *题目的要求：对给出的p序列，求出对应的w序列。
15  */
16 
17 #include <iostream>
18 #include <cstdio>
19 #include <cstring>
20 #include <deque>
21 using namespace std;
22 
23 int main( )
24 {
25 //    freopen("in","r",stdin);
26 //    freopen("out","w",stdout);
27 
28     int T;   ///case数
29     scanf("%d",&T);
30     while( T-- ){
31         int n;
32         scanf("%d",&n);
33         int seq[n];   ///存储输入的p序列
34         for(int i=0 ; i<n ; i++)
35             scanf("%d",&seq[i]);
36 
37         ///用p序列还原括号序列
38         deque<char> parentheses;
39         int existing = 0;
40         for(int i=0 ; i<n ; i++){
41             for(int j=existing ; j<seq[i] ; j++){
42                 parentheses.push_back(‘(‘);
43                 existing++;
44             }
45             parentheses.push_back(‘)‘);
46         }
47 
48         ///输出w序列
49         bool used[2*n];
50         memset(used,0,sizeof(bool)*2*n);
51         for(int i=0 ; i<parentheses.size() ; i++){
52             if( parentheses[i]==‘)‘ ){
53                 int num = 0;
54                 for(int j=i-1 ; j>=0 ; j--){
55                     if( used[j] && parentheses[j]==‘(‘ ){
56                         num++;
57                     }
58                     if( !used[j] && parentheses[j]==‘(‘ ){
59                         num++;
60                         used[j] = true;
61                         break;
62                     }
63                 }
64                 printf("%d ",num);
65             }
66         }
67         cout<<endl;
68     }
69     return 0;
70 }