1880: wjw的火車站
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 140 Solved: 72
[Submit][Status][Web Board]
Description

wjw最近新開了一座火車站…沒錯就是火車站，因為寒假過完同學(xué)們都該返校了，所以他準(zhǔn)備大干一場，但是這里有一個問題，因為wjw的資金不足，所以這座火車站只有一條鐵路，所有的火車從一側(cè)進(jìn)入，從另一側(cè)出來，但是為了方便調(diào)度火車，所以wjw機(jī)智的修改了一下鐵路。如下圖，如果火車A首先進(jìn)入鐵路，然后火車B在火車A離開之前進(jìn)入鐵路，則火車A只有在火車B離開后才能離開。那么現(xiàn)在問題來了，有一串火車按給定順序進(jìn)入車站，wjw希望在通過他的一波操作使這列火車以另一個順序開出火車站，但是他的智商并不支持他解決這個問題，所以你的任務(wù)是確定在給定進(jìn)站順序和出站順序的情況下，給出調(diào)度操作。

Input

輸入包含多組數(shù)據(jù)。每個測試數(shù)據(jù)包含一個正整數(shù)n表示火車數(shù)，接下去的兩個序列表示進(jìn)站順序和出站順序，火車編號為小寫或大寫字母，(a≠A）

Output

輸出數(shù)據(jù)包含一個字符串“Yes.”或“No.”，表示是否有可行的調(diào)度方案，若有，則輸出調(diào)度操作。

Sample Input

3 ABC CBA
3 abc cab

Sample Output

Case #1: Yes.
in
in
in
out
out
out
Case #2: No.

HINT

Source

AC_code:

#include <stdio.h> #include <stack> #include <string.h> using namespace std; char a[1000],b[1000]; int c[1005],k; bool Ans(char *a,char *b,int n) {stack<char>s;int i = 0,j = 0;k = 0;s.push(a[i]);c[k++] = 1;while(i < n&&j < n){if(!s.empty()&&s.top()==b[j]){s.pop();c[k++] = 0;j++;}else if(s.empty()||a[i]!=b[j]){i++;s.push(a[i]);c[k++] = 1;}}if(s.empty())return true;return false; } int main() {int n,t = 0;while(~scanf("%d %s %s",&n,a,b)){printf("Case #%d: ",++t);if(Ans(a,b,n)){printf("Yes.\n");for(int i = 0; i < k; i++){if(c[i])printf("in\n");elseprintf("out\n");}}elseprintf("No.\n");memset(a,'\0',sizeof(a));memset(b,'\0',sizeof(b));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的1880: wjw的火车站(栈)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。