夜之家
这曾经是我的最爱
夜之护者 发表于 2007-07-18 20:36:01
Train Problem I
夜之护者 发表于 2007-07-18 20:26:04
http://acm.hdu.edu.cn/showproblem.php?pid=1022 Train Problem I
也是今天做的，MS代码还算短，也帖下吧。不过主要是因为刚申请的博客，呵呵！
#include<stdio.h>
#define MAXN 1000
int main()
{
long n,i,j,top,num2,x[MAXN],num,flag;
char s1[MAXN],s2[MAXN],a[MAXN];
while(scanf("%ld",&n)==1)
{
scanf("%s%s",s1,s2);
num2=num=0;
top=flag=0;
a[0]=-1;
for(i=0;i<n;i++)
{
a[top++]=s1[i];
x[num++]=1;
while(a[top-1]==s2[num2])
{
top--;
num2++;
x[num++]=0;
}
}
if(num2<n)
printf("No.\nFINISH\n");
else
{
printf("Yes.\n");
for(i=0;i<num;i++)
{
if(x[i])
printf("in\n");
else
printf("out\n");
}
printf("FINISH\n");
}
}
return 0;
}
注释就不写了，就是栈的应用，或许以后有空会来添注释吧，^_^。
很久没一次AC了
夜之护者 发表于 2007-07-18 20:13:52
可能是因为太简单了吧，已知前序遍历和中序遍历，求后序遍历。个人觉得对数据结构初学者来说，这题目挺好的，像我，所以做出来挺开心的，虽然是高中已经写过的东西了。
以下为代码：
#include<stdio.h>
#include<string.h>
#define MAXN 1010
long n,num,total,pre[MAXN],in[MAXN],post[MAXN],hash[MAXN];
struct node
{
long num;
node *left_child,*right_child;
}a[MAXN];
void travel(node *p,long left,long right)
{
long now,i,mid;
if(num>n)
return;
if(left>right)
return;
now=total;
a[now].num=pre[num++];
a[now].left_child=a[now].right_child=NULL;
now=total;
for(i=left;i<=right;i++)
{
if(in[i]==a[now].num)
{
mid=i;
break;
}
}
if(left<=mid-1)
{
a[now].left_child=&a[++total];
travel(&a[total],left,mid-1);
}
if(mid+1<=right)
{
a[now].right_child=&a[++total];
travel(&a[total],mid+1,right);
}
}
void print(node *root)
{
if(root->left_child!=NULL)
{
print(root->left_child);
}
if(root->right_child!=NULL)
{
print(root->right_child);
}
if(root->left_child==NULL&&root->right_child==NULL)
{
if(num)
printf(" ");
else
num=1;
printf("%ld",root->num);
return;
}
if(num)
printf(" ");
else
num=1;
printf("%ld",root->num);
}
int main()
{
long i;
while(scanf("%ld",&n)==1)
{
for(i=0;i<n;i++)
{
scanf("%ld",&pre[i]);
}
for(i=0;i<n;i++)
{
scanf("%ld",&in[i]);
}
num=total=0;
travel(&a[0],0,n-1);
num=0;
print(&a[0]);
printf("\n");
}
return 0;
}
和其他人的比起来好像长了点，不过效率还是瞒高的，呵呵！