NOJ 二零一五年陕西省程序设计竞赛网络预赛（正式赛）(小女警的异世界之战-前序中序求后序)

NOJ 2015年陕西省程序设计竞赛网络预赛（正式赛）(小女警的异世界之战-前序中序求后序)
A - 小女警的异世界之战
Time Limit: 1000 ms Memory Limit: 65536 KB
Submit
Description
这一天，小女警花花，泡泡和毛毛来到终极Boss"Him"所在的异世界并准备与其决一死战，却被困在了他的城堡里。她们发现异世界是一个巨大的城堡。城堡由一个个大小不同的房间组成，房间有着以下的规则：
每个房间有且仅有一扇黄门，此外至多有一扇红门和一扇绿门：黄色代表通向更大的房间，绿色和红色代表通向更小的房间。很显然，如果你打开了一扇红/绿色的门，你会发现门的背面是黄色的，反之同理。
红色和绿色的门都是可以随意打开的，然而黄色的门要等到该房间其他门均被打开过，且该房间怪物已经被杀死时才能被打开。在成功穿过黄门后，这扇门就会消失。
每个房间都会有一个怪物，小女警可自由挑选打败怪物的时机而不影响其打开该房间的红/绿门。
三位小女警的起点就是一间较为特殊的房间，这个房间与正常房间的区别是黄门是特制的。为了解锁这个房间的特殊黄门，三位小女警必须分别依次探索这个房间的其他门，而每个小女警在探索时，怪物与门的状态都会重置。三位小女警的探索方式有着巨大的差别：
花花对红色有着狂热的痴迷，因此当她看见红门时，会暂时无视怪物而立刻冲进去，但是当所在房间没有红门时，她会恢复理智并优先将所在房间的怪物杀死，然后进入绿门（如果有的话）来解锁黄门。
泡泡有强烈的强迫症而且讨厌绿色，当她看到怪物时一定会将其杀死，然后她会优先开启红门，不得已时她才会进入绿门来解锁黄门。
毛毛有拖延症，因此她会优先去开她喜爱的红色的门，随后去开绿色的门，当其所在房间没有门可开时，她才会通过杀死怪物的方式解锁黄门并回去。
每个房间的怪物都有独一无二的名字，当小女警杀死怪物时，怪物的名字会按顺序被记录在日志上，现在花花和泡泡已经按规则探索过了这个城堡，并回到了出发点，毛毛借来了她们的日志以便预测她将会碰到的怪物的顺序，你能帮助她完成这个任务吗？

Input
数据有多组，每组数据以一个数字n(1<=n<=100)为开始，代表有n条记录，
接下来的两行分别是花花和泡泡的日志，分别包含了n个怪物的名字，用空格隔开。
n==0时，输入结束。

Output
输出一行毛毛的日志，怪物名字之间用空格隔开。
Sample Input
5
skeleton zombie spider bat witch
bat zombie skeleton spider witch
0
Sample Output
skeleton spider zombie witch bat
Hint

本题前序中序已知，求后序

注意：class str{char s[MAXN]}s; 这个函数不能写printf("%s",s)要写s.s *不报错

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<map>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (100+10)
#define MAXL (1000+10) 
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n;
int h2[MAXN];
class str
{
public:
//	int i; 
	char s[MAXL]; 
	void mem(){s[0]=0;}
	friend bool operator<(str a,str b){return strcmp(a.s,b.s)<0;	}
	friend bool operator==(str a,str b){return strcmp(a.s,b.s)==0;	}
}s1[MAXN],s2[MAXN];

map<str,int> h;
bool fl;
void dfs(int l1,int r1,int l2,int r2) 
{
	if (l1<r1&&l2<r2)
	{
		int p=h2[l2];
		int len1=p-l1;
		if (len1>0) dfs(l1,p-1,l2+1,l2+len1);
		if (r1-l1+1-len1-1>0) dfs(p+1,r1,l2+len1+1,r2);
	}
	if (fl) printf(" ");else fl=1; 
	printf("%s",s2[l2].s);
}
int main()
{
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	
	while(scanf("%d",&n)==1)
	{
		h.clear();
		if (n==0) return 0;
		For(i,n) s1[i].mem(),s2[i].mem();
		For(i,n) scanf("%s",s1[i].s);
		For(i,n)
		{
			h[s1[i]]=i;
		}
		For(i,n){
			scanf("%s",s2[i].s);
			h2[i]=h[s2[i]]; 
		}
		
		fl=0;
		dfs(1,n,1,n);
		printf("\n");
	}
	return 0;
}

NOJ 二零一五年陕西省程序设计竞赛网络预赛（正式赛）(小女警的异世界之战-前序中序求后序)

相关推荐