3673 - 括号
时间限制 : 1 秒
内存限制 : 128 MB
S1，S2…S2N是一个很好的括号。有两种不同的方式编码：
<span style="font-size:14px;">有一个整数序列P1、P2 ，P =…PN，其中 Pi 是 S 的第 i 个右括号前面的左括号个数。。</span>
<span style="font-size:14px;">有一个整数序列W = W1，W2…WN，对于 S 中的某一个右括号 a，Wi 是从与 a 匹配的左括号开始数起，数到</span>
<span style="font-size:14px;"> a 为止的右括号个数。</span>
<span style="font-size:14px;">以下是上述编码的一个例子：</span>
<span style="font-size:14px;">S（（（（）（）（））））</span>
<span style="font-size:14px;">序列 </span><span style="font-size:14px;">4 5 6 6 6 6</span>
<span style="font-size:14px;"> 1 1 1 4 5
6
<span style="font-size:14px;">写一个程序来转换编码</span>
题目输入
输入的第一行包含一个整数T（1≤t≤10），为测试用例的数量，每个测试案例的第一行是一个整数N（1 < =
n≤20），第二行是一个P字符串序列包含n个正整数，中间用空格隔开。
题目输出
对于每一个测试案例，输出行包含N个整数描述对应给定字符串的W序列。中间用空格隔开。
输入/输出样例
输入格式
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
C语言解答
#include<stdio.h> #include<string.h> int main() { int i,j,p[25]={0},w[25],t,n,k,c,x; while(scanf("%d",&t)==1) { for(;t;t--) { scanf("%d",&n); x=0;c=0; memset(p,0,sizeof(p)); memset(w,0,sizeof(w)); for(i=0;i<n;i++) { scanf("%d",&k); if(c==k)p[++x]=2; else{ while(c<k) if(p[x]==0){p[x++]=1;c++;} else if(p[x]==1){c++;x++;} else x++; p[x]=2; } } for(i=0;i<=x;i++) { if(p[i]==2) { for(j=i-1,c=0;j>=0;j--) { if(p[j]==2)c++; if(p[j]==1&&w[j]==0){ if(i==x)printf("%d",c+1); else printf("%d ",c+1); w[j]=1;break;} if(j==0)printf("0 "); } } } printf("\n"); } } return 0; }
C++解答
#include <stdio.h> int main(){ char s[150],*p,*q; int a,b; int rp,lp,lmp,is_match; int t,n,i,j; scanf("%d",&t); while(t--){ scanf("%d",&n); a=0,b=0; p=&s[0]; j=n; while(j--){ scanf("%d",&b); i=b-a; while(i--) *p++='('; *p++=')'; a=b; } *p='\0'; p=&s[0]; while(*p++){ rp=0,lp=0; is_match=0; if(*p==')'){ q=p-1; while(*q=='('||*q==')'){ if(*q==')'){ rp++; } else if(*q=='('){ if(!rp) is_match=1; else rp--; lp++; } if(is_match){ printf("%d",lp); break; } q--; } if(!is_match) printf("%d",0); if(--n>0) printf(" "); } } if(t) printf("\n"); } return 0; }