括号编码 |
|||||||||||||||||||||||||||||||||||||||||
Time Limit : 1000 MS | Memory Limit : 65536 KB | ||||||||||||||||||||||||||||||||||||||||
Description |
|||||||||||||||||||||||||||||||||||||||||
S = s1 s2...s2n 是一个符合格式的括号的字符串,S能按下面两种方式编码:
请写一个程序将P序列转换成W序列。
第一行是一个整数K,表示有多少个测试用例,以后每两行一个测试用例。每个测试用例第一行为一个整数n(1 <= n <= 20),表示P序列长度,每个测试用例第二行n个非负整数,每个整数之间有一个空格分隔。
每行输出一个测试用例的结果。每行包括n个整数,每个整数之间用一个空格分隔。 |
|||||||||||||||||||||||||||||||||||||||||
Sample Input |
|||||||||||||||||||||||||||||||||||||||||
264 5 6 6 6 694 6 6 6 6 8 9 9 9 |
|||||||||||||||||||||||||||||||||||||||||
Sample Output |
|||||||||||||||||||||||||||||||||||||||||
1 1 1 4 5 61 1 2 4 5 1 1 3 9 参考代码: #include<iostream> #include<cstdio> using namespace std; int a[1000],stack[1000],count[1000]; char str[1010]; int main() { int cases,n,t,i,j,s,sum,top; cin>>cases; while(cases--) { cin>>n; s=0;a[0]=0;sum=0; for(i=1;i<=n;i++) { cin>>a[i]; t=a[i]-a[i-1]; for(j=1;j<=t;j++) { str[++s]='('; count[s]=sum; } str[++s]=')';sum++;count[s]=sum; } top=0; for(i=1;i<s;i++) { if(str[i]=='(') stack[++top]=i; else printf("%d ",count[i]-count[stack[top--]]); } printf("%d ",count[i]-count[stack[top--]]); }return 0; } |