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).
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
思路：
先将数字转换为字符串，然后只要判断出现右括号时往前推找到最近的左括号，标记下左括号代表已经和右括号结合过了，同时统计下在最近的没标记过的左括号之间有几个被标记过的，加起来
就是包含的括号数。题目没什么坑点，想到思路就能做出来了
实现代码：
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<list>
using namespace std;
#define ll long long
const int Mod = 1e9+;
const int inf = 1e9;
const int Max = 1e5+;
vector<int>vt[Max];
//void exgcd(ll a,ll b,ll& d,ll& x,ll& y){if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}
//ll inv(ll a,ll n){ll d, x, y;exgcd(a,n,d,x,y);return (x+n)%n;} ��Ԫ
//int gcd(int a,int b) { return (b>0)?gcd(b,a%b):a; } ��С��Լ
//int lcm(int a, int b) { return a*b/gcd(a, b); } ������
int main()
{
int n,m,i,j,a[],c[],vis[],ans;
char b[];
cin>>n;
while(n--){
cin>>m;
memset(vis,,sizeof(vis));
for(i=;i<m;i++)
cin>>a[i];
for(i=;i<*m;i++)
b[i] = '(';
for(i=;i<m;i++)
b[a[i]+i] = ')';
for(i=;i<m;i++){
ans = ;
for(j=a[i]+i-;j>=;j--){
if(b[j]=='('&&vis[j]==)
ans++;
else if(b[j]=='('&&vis[j]==){
vis[j]=;
ans++;
c[i] = ans;
break;
}
}
}
for(i=;i<m-;i++)
cout<<c[i]<<" ";
cout<<c[m-]<<endl;
}
return ;
}