Parencodings
Time Limit: 1000MS |
|
Memory Limit: 10000K |
Total Submissions: 11191 |
|
Accepted: 6590 |
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-sequence4 5 6666
W-sequence1 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
Source
先说说题目的意思吧,这道题是关于括号匹配的题目
首先输入一个t代表测试数据组数,紧接着输入n,代表右括号的数量
然后在输入n个数,代表每一个右括号的前面有多少个左括号
现在他的问题是,通过输入的数据判断,每一个右括号中间包括了多少对完整的括号
举个例子:(()())
第一个右括号中只括下了他自己一对括号,即1
第二个右括号和第一个情况一样,也是1
但是第三个右括号中间就扩了两个括号进去(()())
这道题,我最先开始想的是利用回溯算法来统计个数,可是怎么也没写对,杯具了很久之后想到直接统计右括号数量并且向前模拟的方法,然后很快就AC了。。后来仔细看了两份代码,发现,改的第一次写的代码中间已经用到了第二次写的一些思路,只不过大体的方向搞错了,所以一直有问题,不过从理论上讲,利用回溯法也应该可以AC,不过可能要麻烦许多。。。
AC代码:
Source Code
Problem: 1068
|
|
User: bingshen
|
Memory: 176K |
|
Time: 0MS |
Language: C++ |
|
Result: Accepted
|
-
Source Code
#include<stdio.h>
#include<string.h>
char s[100];
int p[100];
int right[100];
int w[100];
int ans[100];
int main()
{
int i,n,t,l,j,num;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(p,0,sizeof(p));
memset(w,0,sizeof(w));
memset(s,'(',sizeof(s));
memset(right,0,sizeof(right));
l=0;
num=0;
for(i=1;i<=n;i++)
{
scanf("%d",&p[i]);
if(i==1)
right[i]=p[i]+1;
else
right[i]=right[i-1]+(p[i]-p[i-1])+1;
}
for(i=1;i<=n;i++)
s[right[i]]=')';
int lc=0,rc=0;
for(i=1;i<=n;i++)
{
for(j=right[i];j>=1;j--)
{
if(s[j]=='(')
lc++;
if(s[j]==')')
rc++;
if(lc==rc)
break;
}
printf("%d ",rc);
lc=0;
rc=0;
}
printf("/n");
}
return 0;
}
附一份用回溯写的Wrong Answer程序
Source Code
Problem: 1068
|
|
User: bingshen
|
Memory: N/A |
|
Time: N/A |
Language: C++ |
|
Result: Wrong Answer
|
-
Source Code
#include<stdio.h>
#include<string.h>
char s[100];
int p[100];
int right[100];
int w[100];
int ans[100];
int dfs(int l,int r)
{
int lc=0,rc=0,i,sum=0,start;
if(l==r-1)
return 1;
else
{
start=l+1;
for(i=l+1;i<=r-1;i++)
{
if(s[i]=='(')
lc++;
if(s[i]==')')
rc++;
if(lc==rc)
{
w[i]=dfs(start,i);
sum=sum+w[i];
lc=0;
rc=0;
start=i+1;
}
}
return sum+1;
}
}
int main()
{
int i,n,t,l,j,num;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(p,0,sizeof(p));
memset(w,0,sizeof(w));
memset(s,'(',sizeof(s));
memset(right,0,sizeof(right));
l=0;
num=0;
for(i=1;i<=n;i++)
{
scanf("%d",&p[i]);
if(i==1)
right[i]=p[i]+1;
else
right[i]=right[i-1]+(p[i]-p[i-1])+1;
}
for(i=1;i<=n;i++)
s[right[i]]=')';
w[right[n]]=dfs(1,right[n]);
for(i=1;i<=right[n];i++)
{
if(w[i])
ans[num++]=w[i];
}
if(num==0)
printf("/n");
for(i=0;i<num-1;i++)
printf("%d ",ans[i]);
printf("%d/n",ans[num-1]);
}
return 0;
}
分享到:
相关推荐
北大POJ1068-Parencodings 解题报告+AC代码
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
poj 百练 题目分类 poj 百练 题目分类
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案
选择了三道经典的二分查找的poj模拟题,有利于读者对二分查找的深刻把握
poj2340,模拟题,使用两个优先队列模拟即可。