Parencodings
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 13268 Accepted: 7886
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:
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
题目大意:一个完备的括号串(即所有括号都可以成功匹配)可以以2种编码方式编码
P型编码,在右括号出现的位置的值为,之前左括号出现的次数。
W型编码,在右括号出现的位置的值为,一个以该括号为终点的子完备括号串中右括号的个数。
输入一个括号串的P型编码,要求求出W型编码。
代码:
#include<iostream>
using namespace std;
int p[22];
int w[22];
int main()
{
int t;
cin>>t;
int n;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>p[i];
w[0] = 0;
p[0] = 0;
for(int i=1;i<=n;i++)
{
int val = p[i]-p[i-1];
if(val>0)
{
w[i] = 1;
}
else
{
int temp = 1;
int cnt = 1;
for(int j=i;j>=1;j--)
{
temp--;
temp+=p[j]-p[j-1];
if(temp>0)
{
w[i] = cnt;
break;
}
else
cnt++;
}
}
}
for(int i=1;i<=n;i++)
{
if(i!=1)
cout<<" "<<w[i];
else
cout<<w[i];
}
cout<<endl;
}
return 0;
}
分享到:
相关推荐
【POJ1068-Parencodings】是北京大学在线编程平台POJ上的一道经典题目,主要涉及到了字符串处理和动态规划的概念。这道题目要求我们计算一个给定长度的字符串有多少种不同的括号编码方式,即平衡括号序列。括号序列...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...
标签"poj poj_27 poj27 poj2775"进一步确认了这是一道关于POJ平台的编程挑战,其中"poj_27"可能是表示第27类问题或者某种分类,而"poj27"可能是对"poj2775"的简写。 压缩文件中的"www.pudn.com.txt"可能是一个链接...
标题中的"poj_2682(3).rar"是一个指向编程竞赛问题的引用,通常这类问题在网站如POJ(Programming Online Judge)上出现,供程序员解决并提交代码进行测试。这个问题的编号是2682,可能涉及到特定的数据结构或算法...
标题中的“pku1151.rar_Atlantis_pku 11_poj Atlant_poj Atlantis_poj11”似乎是指北京大学(Peking University, PKU)编程竞赛中的一道题目,编号为1151,与“Atlantis”这个主题相关。这道题目在多个平台上也被提及...
标题中的“poj2488.rar_poj24_poj2488_方向模板法”指的是一个解决编程竞赛问题POJ2488的压缩文件,其中可能包含了解决该问题的代码示例。POJ是Programming Online Judge的缩写,是一个在线的编程竞赛平台,参与者...
《POJ 1010 Stamps:解题思路与陷阱分析》 POJ 1010,也被称为“邮票问题”,是编程竞赛中的一道经典题目,旨在考察参赛者的动态规划和数学思维能力。这个题目在编程爱好者中具有较高的知名度,因为它涉及到有趣的...
【标题】"POJ3601.rar" 是一个压缩包文件,主要包含了对北京大学在线评测系统(Online Judge)上的一道题目——POJ 3601的解答和相关实验报告。"POJ 3601"是这道编程问题的编号,通常在编程竞赛或练习平台中,每个...
标题中的“poj1038--Bugs.rar”是一个关于解决编程竞赛问题的压缩文件,其中包含了对“Bugs”问题的解答。POJ(Problemset Online Judge)是一个在线编程竞赛平台,它提供了一系列的问题供参赛者解决,旨在锻炼和...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...
标题 "ACM.zip_ACM_poj_poj3187_poj3669" 提供的信息表明,这个压缩包包含的是与ACM(国际大学生程序设计竞赛)相关的编程题目解决方案,具体是POJ(Programming Online Judge)平台上的两道题目,编号分别为poj3187...
标题“POJ14_MONI2.zip”暗示这是一个与编程竞赛相关的压缩文件,很可能包含了某个特定问题的解决方案或代码示例。"POJ"通常指的是“Programming Online Judge”,这是一个在线编程竞赛平台,让参赛者解决各种算法...
【标题】"POJ1753.rar_poj 1753_poj1753" 提供的资源是关于POJ1753编程挑战的解决方案,其中包括了完整的代码实现以及实验报告。POJ(Problem Online Judge)是中国大学常用的在线编程竞赛平台,它提供了一系列的...
标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...
标题中的"string-problem(POJ).rar_POJ 19_poj"表明这是一个与ACM编程竞赛相关的压缩包,特别关注的是字符串处理问题。在ACM编程竞赛中,字符串问题是一个常见的类别,通常涉及到字符串的查找、比较、操作、模式匹配...
《POJ 1990:树状数组解题策略详解》 在编程竞赛的世界里,POJ(Programming Online Judge)是一个备受瞩目的在线评测系统,它提供了丰富的编程题目供参赛者挑战。其中,编号为1990的题目是一道涉及数据结构与算法...
标题中的"POJ3322.rar_poj33_www.3322.se.c"暗示这是一个关于编程竞赛的问题,POJ(Problem Online Judge)是著名的在线编程竞赛平台,而"3322"是该平台上问题的编号。这个问题可能是从www.3322.se.c这个网站上获取...
《多种解题技巧在POJ1035_Spelling Checker中的应用》 在编程竞赛领域,ACM(国际大学生程序设计竞赛)是一项备受瞩目的赛事,它要求参赛者在有限的时间内解决一系列复杂的算法问题。POJ(Problemset Online Judge...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...