Parencodings
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 13525 |
|
Accepted: 8049 |
Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).
Following is an example of the above encodings:
S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.
Output
The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.
Sample Input
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9
有點亂，感覺方法好多，就是不知道怎么寫……
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 int t,n,a[30];
5 int sec,i,j,k,top;
6 int stack[50],ans[50];
7 void printtest()
8 {
9 int i;
10 for (i=1;i<=top ;i++ )
11 if (stack[i]==-1) printf("(");
12 else printf(")");
13 }
14 int main()
15 {
16 scanf("%d",&t);
17 for (j=1;j<=t ;j++ )
18 {
19 scanf("%d",&n);
20 a[0]=0;
21 top=0;
22 for (i=1;i<=n ;i++ )
23 {
24 scanf("%d",&a[i]);
25 if (a[i]!=a[i-1])
26 {
27 for (k=a[i-1]+1;k<=a[i] ;k++ )
28 {
29 top++;
30 stack[top]=-1;//-1表示右括號
31 }
32 top++;
33 stack[top]=1;//1表示左括號
34 }
35 else
36 {
37 top++;
38 stack[top]=1;
39 }
40 }
41 //printtest();//檢查
42 ans[0]=0;
43 for (i=1;i<=top ;i++ )
44 if (stack[i]==1)
45 {
46 sec=1;
47 k=i-1;
48 while (sec!=0)
49 {
50 sec=sec+stack[k];
51 k--;
52 }
53 ans[0]++;
54 ans[ans[0]]=(i-k+1)/2;
55 }
56 for (i=1;i<ans[0] ;i++ ) printf("%d ",ans[i]);
57 printf("%d\n",ans[ans[0]]);
58 }
59 return 0;
60 }
61