学步园

模拟题目，先把P转换成 字符串 ，然后在求 W

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). 

题目很绕，看了会题目，翻一下。

对第 i  个右括号，pi  的意思是前面有几个左括号。

（W更绕）

对第 i  个右括号，wi  的意思是：从于它配对的左括号到它本身（包括），右括号的个数。

我做的时候把配对的括号变成了空格，这样数出来 空格的个数/2 就是右括号的个数。

 

 

MDK

1068

Accepted

172K

0MS

C++

1915B

2011-11-07 19:42:32

int main() {
//FOPEN
    int cas;SCF(cas);
int a[MAXN];
while(cas--) {
int n;SCF(n);
        F(i,n) SCF(a[i]);

char ss[MAXNT];
int cp=0,ans = 0;
        F(i,n) {
if(i == 0)
                F(j,a[i]) {
                    ss[cp++] = '(';
                }
else {
                F(j,a[i] - a[i-1])
                    ss[cp++] = '(';
            }
            ss[cp++] = ')';
        }
        F(i,cp) {
if(ss[i] == ')') {
int numbla = 0,pre = 0;
for(pre = i;pre>=0;pre--,numbla++) {
if(ss[pre] == '(') {
break;
                    }
                }
                ss[pre] = '';ss[i] = '';
                a[ans ++] = numbla / 2 + 1;
            }
        }
        printf("%d",a[0]);
        FOR(i,1,ans-1) printf(" %d",a[i]);
        puts("");
    }
}