首页 > 代码库 > POJ 1068-Parencodings(模拟)
POJ 1068-Parencodings(模拟)
Parencodings
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 20444 | Accepted: 12303 |
Description
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).
Following is an example of the above encodings:
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
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
思路:b[i]表示第i和i+1个右括号之间有多少个括号,然后逐渐找和右括号匹配的左括号的位置。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; int main() { int T,n,i,j; int a[110],b[110],c[110]; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d",&a[i]); } b[0]=a[1]; for(i=1; i<n; i++) { b[i]=a[i+1]-a[i]; } for(i=1; i<=n; i++) { for(j=i-1; j>=0; j--) { if(b[j]>0) { b[j]--; break; } } c[i]=i-j; } for(i=1; i<n; i++) printf("%d ",c[i]); printf("%d\n",c[i]); } return 0; }
POJ 1068-Parencodings(模拟)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。