hdu5444 模拟

题目大意：给你一棵树的先序遍历和中序遍历，让你求给定点的位置。

算法思路：根据中序遍历和先序遍历的特点，模拟即可（这模拟模了我快三小时，我也是醉了）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define MAXN 1005
string str[MAXN];
int t,n,q;
int a[MAXN],b[MAXN];
bool visited[MAXN];
int main()
{
    scanf("%d",&t);

    while(t--)
    {
        memset(visited,false,sizeof(visited));
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }

        for(int i=1; i<=n; i++)
        {
            str[i]="";
        }
        for(int i=1; i<=n; i++)
        {
            b[a[i]]=i;
        }
        visited[a[1]]=true;
        //左子树
        for(int i=2; i<=a[1]; i++)
        {
            if(a[i]<a[i-1])
            {
                str[a[i]]=str[a[i-1]]+'E';
                visited[a[i]]=true;
            }
            else if(a[i]>a[i-1])
            {
                int f=a[i];
                while(f>1)
                {
                    f--;
                    if(visited[f]&&b[f]<b[a[i]])
                        break;
                }
                str[a[i]]=str[a[b[f]]]+'W';
                visited[a[i]]=true;
            }
        }
        //右子树
        int k=1+a[1];
        if(a[k]<a[1])
        {
            str[a[k]]=str[a[1]]+'E';
            visited[a[k]]=true;
        }
        else if(a[k]>a[1])
        {
            int f=a[k];
            str[a[k]]=str[a[1]]+'W';
            visited[a[k]]=true;
        }

        for(int i=a[1]+2; i<=n; i++)
        {
            if(a[i]<a[i-1])
            {
                str[a[i]]=str[a[i-1]]+'E';
                visited[a[i]]=true;
            }
            else if(a[i]>a[i-1])
            {
                int f=a[i];
                while(f>a[1])
                {
                    f--;
                    if(visited[f]&&b[f]<b[a[i]])
                        break;
                }
                str[a[i]]=str[a[b[f]]]+'W';
                visited[a[i]]=true;
            }
        }

        scanf("%d",&q);
        for(int i=1; i<=q; i++)
        {
            int x;
            scanf("%d",&x);
            cout<<str[x]<<endl;
        }

    }
}