题目背景
四川2008NOI省选
题目描述
斜堆(skew heap)是一种常用的数据结构。它也是二叉树，且满足与二叉堆相
同的堆性质：每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。
但斜堆不必是平衡的，每个结点的左右儿子的大小关系也没有任何规定。在本题
中，斜堆中各个元素的值均不相同。
在斜堆 H 中插入新元素X 的过程是递归进行的：当H 为空或者X 小于H
的根结点时X 变为新的树根，而原来的树根（如果有的话）变为X 的左儿子。
当X 大于H 的根结点时，H 根结点的两棵子树交换，而X（递归）插入到交换
后的左子树中。
给出一棵斜堆，包含值为0~n的结点各一次。求一个结点序列，使得该斜堆
可以通过在空树中依次插入这些结点得到。如果答案不惟一，输出字典序最小的
解。输入保证有解。
输入输出格式
输入格式：第一行包含一个整数n。第二行包含n个整数d1, d2, ... , dn， di<100表示i
是di的左儿子，di>=100 表示i 是di-100 的右儿子。显然0 总是根，所以输入中
不含d0。
输出格式：仅一行，包含n+1整数，即字典序最小的插入序列。
输入输出样例
6
100 0 101 102 1 2
0 1 2 3 4 5 6
6
100 0 2 102 4 104
4 6 5 2 0 1 3
7
0 100 1 102 2 3 5
2 5 0 3 4 6 7 1
说明
2 <= n <= 50
Solution：
这题，ZYYS～，真人类智慧题啊。
考虑斜堆中最后插入的那个结点，容易发现：
（1）它一定是一个极左结点（就是从根往它的路上一直都是沿着左链走），因为插入的时候每次都是插入到左子树中；
（2）它一定木有右子树，因为插入的时候每次都是把原来的某棵子树作为新结点的左子树；
满足（1）（2）的结点可能有多个，但紧接着可以发现，这个斜堆中的每个结点如果木有左子结点，那么也木有右子结点（或者说，每个非叶结点都有左子树），而在插入一个结点之前，其所有的祖先都被交换了左右子树，所以，若新结点的祖先中有满足（1）（2）的，且新结点不是叶结点，那么在新结点插入之前，这个满足（1）（2）的祖先必然是只有右子树而木有左子树的，这与上面的那个性质矛盾，所以，可以得出：最后插入的那个结点一定是满足（1）（2）的结点中，深度最小的那个（设为X），除非X的左子结点是叶结点，此时为了满足字典序最小，应该取X的左子结点为最后插入的。找到这个最后插入的结点以后，只需要把它删掉，并把它的所有祖先交换左右子树，就是插入该结点以前的状态了。这样可以找到字典序最小的插入顺序。
（反正我自己是想不出的>.^_^.<）
代码：
/*Code by 520 -- 8.28*/ #include<bits/stdc++.h> #define il inline #define ll long long #define RE register #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--) using namespace std; const int N=100; int n,rt,fa[N],ls[N],rs[N],ans[N],cnt; il void pre(){ memset(fa,-1,sizeof(fa)), memset(ls,-1,sizeof(ls)), memset(rs,-1,sizeof(rs)); } il void init(){ int x=rt; while(rs[x]!=-1) x=ls[x]; int t=ls[x]; if(t!=-1&&ls[t]==-1&&rs[t]==-1) x=t; ans[++cnt]=x; if(x==rt) rt=ls[x]; int f=fa[x]; if(f!=-1) ls[f]=ls[x],fa[ls[f]]=f; while(f!=-1) swap(ls[f],rs[f]),f=fa[f]; } int main(){ pre(); scanf("%d",&n); For(i,1,n) { RE int x;scanf("%d",&x); if(x<100) ls[x]=i,fa[i]=x; else rs[x-100]=i,fa[i]=x-100; } For(i,0,n) init(); while(cnt) printf("%d ",ans[cnt--]); return 0; }