HDU

我真是个憨皮，一开始用数组直接建树，忘了会爆，RE3发才知道。然后稍微改了一下树就过了。

题意：按题目意思给出某棵树的访问序列，第一个数为根节点，后一个数如果小于等于根节点则为根节点的右孩子，否则为左孩子，然后在以孩子为根节点按以上规律建树。现在有q个询问，求从根节点出发访问某个节点的路径，如果访问的为左孩子输出‘W’，右孩子输出‘E’。

思路：模拟就完事

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,b,s[1200];
struct node
{
    int l,r;
    int num;
}pp[1200];
queue<string> p[1200];
void dfs(int pos,int nn)
{
    if(pp[pos].l==-1&&pos<s[nn])
    {
           pp[pos].l=s[nn];
           p[s[nn]].push("W");
        return ;
    }
    else if(pp[pos].r==-1&&pos>s[nn])
    {
           pp[pos].r=s[nn];
            p[s[nn]].push("E");
       return ;
    }
    if(s[nn]>pos)
    {
        p[s[nn]].push("W");
        dfs(pp[pos].l,nn);
    }
   else if(s[nn]<pos)
        {
            p[s[nn]].push("E");
            dfs(pp[pos].r,nn);
        }

}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            while(!p[i].empty())p[i].pop();
        }
        for(int i=0; i<n; i++)
        {
             scanf("%d",&s[i]);
             pp[i+1].l=pp[i+1].r=-1;
        }
        p[s[0]].push("");
        for(int i=1; i<n; i++)
        {
            dfs(s[0],i);
        }
        int d;
        scanf("%d",&d);
        for(int i=0; i<d; i++)
        {
            int a;
            scanf("%d",&a);
            while(!p[a].empty())
            {
                cout<<p[a].front();
                p[a].pop();
            }
            printf("
");
        }
    }
    return 0;
}

 附大佬的代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
struct Node{
    Node *lc,*rc;
    int num;
    void clear(){
        num=-1;
        lc=rc=NULL;
    }

}pool[maxn];
Node *root,*cur;
int T,n,a[maxn],q;
Node *newnode()
{
    cur->clear();
    return cur++;
}
void build(Node *root,int value){
    if(root->num==-1){
       root->num=value;
    return;
       }
    if(value>root->num){
        if(root->lc==NULL)root->lc=newnode();
    build(root->lc,value);
    }
    else {
        if(root->rc==NULL)root->rc=newnode();
        build(root->rc,value);
    }
}
inline void init(){
    cur=pool;
    cur->clear();
    root=cur++;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    init();
    root->num=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]>a[1]){
            if(root->lc==NULL)root->lc=newnode();
            build(root->lc,a[i]);
        }
        else {
            if(root->rc==NULL) root->rc=newnode();
            build(root->rc,a[i]);
        }
    }
    scanf("%d",&q);
    for(int i=1,x;i<=q;i++){
        scanf("%d",&x);
        Node *now=root;
        while(x!=now->num){
            if(x>now->num){
                putchar('W');
                now=now->lc;
            }
            else {
                putchar('E');
                now=now->rc;
            }
        }
        puts("");
    }
}

    return 0;
}