【BZOJ1078】[SCOI2008]斜堆（性质题）

题面

BZOJ
洛谷

题解

考虑一下这道题目的性质吧。思考一下最后插入进来的数是什么样子的。首先因为它是最后插入进来的，所以一定是比某个数小，然后把这个数作为一个根，原来的树根直接接到了左儿子上面，因此它没有右儿子。然而显然可以同时有多个儿子没有右子树。再想想，显然的，每次都是交换路径上的左右儿子，然后插入到左儿子中，所以显然最后插入的这个点是一路插进左儿子的。所以每次找到最靠左的、并且没有右儿子的位置，然后再判断一下它的左儿子是否只有一个点，否则优先选左儿子（保证字典序更小）。

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAX 55
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,ch[MAX][2],fa[MAX];
int nw,ans[MAX],rt;
void work()
{
    nw=rt;
    while(ch[nw][1])nw=ch[nw][0];
    int v=ch[nw][0];
    if(v&&!ch[v][0]&&!ch[v][1])nw=v;
}
int main()
{
    n=read();fa[rt=0]=-1;
    for(int i=1;i<=n;++i)
    {
        int x=read();
        if(x<100)ch[x][0]=i,fa[i]=x;
        else ch[x-100][1]=i,fa[i]=x-100;
    }
    for(int i=n;i>=0;--i)
    {
        nw=-1;work();ans[i]=nw;
        if(nw==rt)rt=ch[nw][0];int ff=fa[nw];
        if(~ff)
        {
            ch[ff][0]=ch[nw][0];
            if(ch[nw][0])fa[ch[nw][0]]=ff;
        }
        while(~fa[nw])swap(ch[fa[nw]][0],ch[fa[nw]][1]),nw=fa[nw];
    }
    for(int i=0;i<=n;++i)printf("%d ",ans[i]);
    puts("");return 0;
}

【BZOJ1078】[SCOI2008]斜堆（性质题）

原文：https://www.cnblogs.com/cjyyb/p/9738001.html