Luogu P1377 [TJOI2011]树的序

作者: MayFlyyh 分类: 其他 发布时间: 2018-06-26 15:20 ė 6 1条评论

Luogu P1377 [TJOI2011]树的序

不知道为什么bzoj上没这道题。。

题目描述

众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:1、空树中加入一个键值k,则变为只有一个结点的二叉查找树,此结点的键值即为k;2、在非空树中插入一个键值k,若k小于其根的键值,则在其左子树中插入k,否则在其右子树中插入k。

我们将一棵二叉查找树的键值插入序列称为树的生成序列,现给出一个生成序列,求与其生成同样二叉查找树的所有生成序列中字典序最小的那个,其中,字典序关系是指对两个长度同为n的生成序列,先比较第一个插入键值,再比较第二个,依此类推。

输入格式:
第一行,一个整数,n,表示二叉查找树的结点个数。第二行,有n个正整数,k1到kn,表示生成序列,简单起见,k1~kn为一个1到n的排列。

输出格式:
一行,n个正整数,为能够生成同样二叉查找数的所有生成序列中最小的。

100% n<=100000

题意就是让你按指定次序建树,然后输出该树的前序遍历

显然不能直接暴力建,因为暴力建可能会出现一条链的情况

显然不能用splay。。因为splay会破坏前序遍历顺序

笛卡尔树是一种既能保持heap性质,又能保证BST性质的树(感觉就是treap)..

就heap性质讲,我们可以把需要建立的这个heap看成一个小根堆,越早插入的数的heap值越小,也就是顺次从1-n设立heap值

按值建树

将数列按照Key从小到大排序

这样建树如果要保持BST的性质,那么就是不停的在右链上依次添加就好(因为key是递增的),这样我们满足了BST的性质,现在考虑满足heap的性质

我们需要建立一个小根堆,那么我们就开一个栈,保存右链上的节点,显然栈顶是右链的最后一个结点,栈底是根

这样每次从顶到底找到第一个heap值小于当前Key所对应的heap值的元素,其余的全部作为当前元素的左儿子(比当前元素的Key小且比当前元素的heap大),当前元素作为这个第一个小于当前heap的右儿子(heap比他小但Val比他大)

这样就好了

CODE

#include<bits/stdc++.h>
struct SZ{
    int val,heap,ls,rs;
    SZ(){
        rs=ls=val=heap=0;
    }
    bool operator < (const SZ m) const{
        return val<m.val;
    }
}e[101000];
int ls[100100],rs[100100];
std::stack<SZ> s;
inline int dfs (int v){
    if(!v) return 0;
    printf("%d ",v);
    dfs(ls[v]);
    dfs(rs[v]);
}
int main (){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&e[i].val);
        e[i].heap=i;
    }
    std::sort(e+1,e+1+n);
    for(int i=1;i<=n;++i){
        SZ l,fa;
        while(!s.empty()&&s.top().heap>e[i].heap) l=s.top(),s.pop();
        if(!s.empty()) fa=s.top();
        rs[fa.val]=e[i].val;
        ls[e[i].val]=l.val;
        s.push(e[i]);
    }
    dfs(rs[0]);
    return 0;   
}

按照Heap值建树(自底向上)

保存一个Val的前驱与后继(默认i的前驱是i-1,i的后继是i+1)

存储一下Val 对应的heap值(也就是操作顺序的序号)

按照操作顺序的逆序(n to 1) 建树

每一次操作肯定是找自己的父亲,显然这个父亲是在本次操作之前的前驱或后继

然后比较一下前驱的Heap值与后继的Heap值,哪个越大就接在哪个上面(显然),注意接的时候按照BST的性质接

然后更新一下删除了当前点的前驱后继

#include<bits/stdc++.h>
const int N =100100;
int val[N],rs[N],ls[N],heap[N];
int pre[N],nxt[N];
int dfs(int v){
    if(!v) return 0;
    printf("%d ",v);
    dfs(ls[v]);
    dfs(rs[v]);
} 
int main (){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&val[i]);
        heap[val[i]]=i;
        pre[i]=i-1,nxt[i]=i+1;
    }
    for(int i=n;i>=1;--i){
        int p=pre[val[i]],nx=nxt[val[i]];
        if(heap[p]>heap[nx]) rs[p]=val[i];
        else ls[nx]=val[i];
        pre[nx]=p;nxt[p]=nx;
    }
    dfs(val[1]); 
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/240

一条评论

  1. wjyyy 2018年7月3日 下午6:36 回复

    bzoj上好多题都被隐藏了。。。

wjyyy进行回复 取消回复

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部