2013
12-09

# Parencodings

Let S = s1 s2 … s2n be a well-formed string of parentheses. S can be encoded in two different ways:
• 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).
• 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.

The first line of the input file 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.

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.

2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

mark：因为数据很小，n的长度只有20，因此可以直接模拟，由P反求出S，然后由S直接求出P。

# include <stdio.h>
# include <string.h>

char str[50] ;
int p[50],w[50] ;
int n ;

void setstr()
{
int num, i, j, cnt ;
for(i=0;i<n;i++)
{
scanf ("%d", &num) ;
cnt = 0 ;
for(j=0;cnt<num;j++)
{
if (str[j]==')') continue ;
cnt++ ;
}
while (str[j]==')')j++ ;
str[j] = ')' ;
}
for(i = 0 ; i < 2*n ; i++) if (str[i]!=')') str[i] = '(' ;
str[2*n] = '\0' ;
}

void setw()
{

int i, j=0, flag = 0 ;
for (i = 0 ; i < 2*n ; i++)
{
if (str[i]=='('){ j=i; continue ;}
if (flag == 0) flag = 1 ;
else putchar(' ') ;
printf ("%d", (i-j)/2+1) ;
str[j] = '*' ;
while (j>=0 && str[j] != '(') j-- ;
}
printf ("\n") ;
}

int main ()
{
int t ;
scanf ("%d", &t) ;
while (t--)
{
scanf ("%d", &n) ;
memset (str, 0, sizeof(str)) ;
setstr() ;
setw() ;
}
return 0 ;
}

1. 因为是要把从字符串s的start位到当前位在hash中重置，修改提交后能accept，但是不修改居然也能accept

2. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。