POJ-1068 解题报告

题意简述

字符串s仅由括号构成(e.g.“(((()()())))”)。它可以用以下两种形式编码:

1、P编码: 记录每个右括号前有几个左括号。例如:上面的S串可被表示为:4 5 6 6 6 6;

2、W编码: 记录每对对应的左右括号之间有几个右括号。例如:上面的S串可被表示为:1 1 1 4 5 6

给定测试组数t(1 <= t <= 10),输入每组的右括号数量,和该串的P编码。输出该串的W编码。

算法分析

直接模拟。从读入的P编码中还原原串(我直接还原为01串,0为左括号1为右括号)。

建一个栈。从头向后扫描还原的串。遇到左括号则压入栈内,遇到右括号则出栈,记录下该对左右括号的位置。

扫描每对左右括号间有多少个右括号。输出结果。

Problem Status: AC。时间0ms,内存120k

——————————————————————分割线——————————————————————

优化:

该题POJ排名第一的成绩,耗时0ms,内存0k……太恐怖了……想不到这么神奇的算法……

程序样例

[c]
#include&lt;stdio.h&gt;
int main()
{
int t,i,j,n[20][2],p=0,s[50]={0},tem,stack[50],ans;
scanf("%d",&amp;i);
for(;i&gt;0;i–)
{
scanf("%d%d",&amp;t,&amp;n[0][0]);
for(p=0;p&lt;n[0][0];p++) s[p]=0;
s[p]=1; p++;
for(j=1;j&lt;t;j++)
{
scanf("%d",&amp;n[j][0]);
tem=p+n[j][0]-n[j-1][0];
for(;p&lt;tem;p++) s[p]=0;
s[p]=1; p++;
}
p=0;
for(j=0;j&lt;t*2;j++)
{
if (s[j]==0)
{
stack[p]=j;
p++;
}
else
{
n[(j-p+2)/2-1][0]=stack[p-1];
n[(j-p+2)/2-1][1]=j;
p–;
}
}
for(j=0;j&lt;t;j++)
{
ans=0;
for(p=n[j][0];p&lt;=n[j][1];p++) ans+=s[p];
printf("%d ",ans);
}
printf("n");
}
system("pause");
return 0;
}

[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *