Blog·Tanky WooABOUTRSS

HDU/HDOJ 1022 Train Problem I(栈模拟,简单题)

13 Apr 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1022

简单的栈模拟,可以用STL中的stack做,这样就简化了很多细节,我是自己设置一个数组和一个rear指针的。

先开始判断成while(rear>=0 && i <= n),结果WA了,后来测试 3 123 123就发现了错误,去掉rear>=0,AC~~~

#include 
using namespace std;

int n;
char in[1005];
char out[1005];
char st[1005];
int rear;
int rec[2010], cnt = 0;  // 1--in, -1 ---out

int main()
{
    while(scanf("%d", &n;) != EOF)
    {
        memset(in, 0, sizeof(in));
        memset(rec, 0, sizeof(rec));
        scanf("%s %s", in, out);

        int i=1, j=0;
        st[0] = in[0];
        rec[0] = -1;
        cnt = 1;
        rear = 0;
        while(i <= n)
        {
            if(st[rear] == out[j])
            {
                rec[cnt++] = 1;
                --rear;
                ++j;
            }
            else
            {
                if(i == n)
                    break;
                st[++rear] = in[i++];
                rec[cnt++] = -1;
            }
        }
        if(rear >= 0)
            printf("No.\n");
        else
        {
            printf("Yes.\n");
            for(int i=0; i<2*n; ++i)
                if(rec[i] == -1)
                    cout << "in" << endl;
                else
                    cout << "out" << endl;
        }
        cout << "FINISH" << endl;

    }
}