杭电1002http://acm.hdu.edu.cn/showproblem.php?pid=1022
Train Problem I
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25276 Accepted Submission(s): 9529
3 123 312
in
in
in
out
out
out
FINISH
No.
FINISH
Hint
For the first Sample Input, we let train 1 get in, then train 2 and train 3.
So now train 3 is at the top of the railway, so train 3 can leave first, then train 2 and train 1.
In the second Sample input, we should let train 3 leave first, so we have to let train 1 get in, then train 2 and train 3.
Now we can let train 3 leave.
But after that we can't let train 1 leave before train 2, because train 2 is at the top of the railway at the moment.
So we output "No.".
代码1:
#include<cstdio>
#include<string>
#include<iostream>
#define N 20
using namespace std;
string sc[N];
string in,out;
char str[N];
int main()
{
int t ,i , j ,c , k ;
while(~scanf("%d",&t))
{
in.clear();out.clear();
cin>>in>>out;
j = ;c = ; k =;
for( i = ; i < t ; i++ )
{
str[c]=in[i];
sc[k++]="in";
while(c!=-&&str[c]==out[j])//这儿有点问题,c=0这儿有歧义,有时候栈为空,有时候不空,最好别这么写
//也就是,str有变化的时候,第一时间修改c的值
//这儿就是用混了,写成了c != 0,事实上,这儿c=0的时候,栈里还有一个元素
{
sc[k++] = "out";
c--;j++;
}
c++;
}
if(j==t) {printf("Yes.\n");
for( i = ;i < k ; i++)
printf("%s\n", sc[i].c_str());} //string是不可以printf的,要用c_str函数,转为字符数组
else printf("No.\n");
printf("FINISH\n");//少了换行
}
//system("PAUSE");
return ;
}
代码2:
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
int main()
{
int n, i, j, k, flag[];
char s1[], s2[];
stack <char> s;
while(~scanf("%d %s%s",&n,s1,s2))
{
while(!s.empty()) s.pop(); //也可以不写这一句,把 stack <char> s; 就可以了
memset(flag,-,sizeof(flag));
j = k = ;
for(i = ; i < n; i++)
{
s.push(s1[i]);
flag[k++] = ;
while(!s.empty() && s.top() == s2[j])
{
flag[k++] = ;
s.pop();
j++;
}
}
if(j == n)
{
printf("Yes.\n");
for(i = ; i < k; i++)
{
if(flag[i])
printf("in\n");
else
printf("out\n");
}
}
else
printf("No.\n");
printf("FINISH\n");
}
return ;
}
代码3:(感谢提供代码的伟大帅气的松哥~)
#include <cstdio>
using namespace std; int main()
{
int n;
char o1[], o2[];
int stack[];
bool ans[];
while(~scanf("%d", &n))
{
scanf("%s %s", o1, o2);
int top = , cur = , c = ;
for(int i = ; i < n; i++)
{
stack[top++] = o1[i]-'';
ans[c++] = ;
while(top > && stack[top-] == o2[cur]-'')
{
top--;
cur++;
ans[c++] = ;
}
}
if(top > ) puts("No.");
else
{
puts("Yes.");
for(int i = ; i < c; i++)
{
if(ans[i] == ) puts("out");
else puts("in");
}
}
puts("FINISH");
}
return ;
}