首页 > 代码库 > BZOJ1078 [SCOI2008]斜堆
BZOJ1078 [SCOI2008]斜堆
一个巨坑总算是填上了。。。
从十一开始调直到今天才过掉，已经交了上50次了。。。在无数RE后才发现，本地评测真是啃爹啊啊啊啊！！！
Mato大神说的好："其实是一个超级大水题"。。。我是蒟蒻又被虐了。。。
对于斜堆插入的最后一个节点，可以推出两点性质：
(1)它一定是一个树中的极左节点
(2)它肯定没有右子树
然后又可以发现，所有斜堆中的点，如果他没有左子树，也不会有右子树。（就是非叶子必有左子树，废话吧。。。）
然后Mato balabala说了一堆。。。（看不懂。。。）得到最终结论：
最后插入的节点X，必然是满足(1)(2)，且深度最小，除非他的左子树只有一个节点。（为了满足插入队列最小）
所以做法是：
(1)按照上面的结论找到当前插入的节点
(2)删掉该点
(3)把它的祖先的左右子树都交换了
就做完了
1 /************************************************************** 2 Problem: 1078 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:0 ms 7 Memory:812 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 15 struct heap{16 int lson, rson, fa;17 heap(){18 lson = rson = fa = -1;19 }20 }h[300];21 22 int n, X, ans[300], root;23 24 void work(){25 int cnt = n + 1, p, fa, son;26 bool flag;27 while (cnt){28 flag = 0;29 p = root;30 while (h[p].rson != -1) p = h[p].lson;31 son = h[p].lson;32 if (son != -1 && h[son].lson == - 1 && h[son].rson == -1) 33 p = son;34 ans[cnt--] = p;35 36 fa = h[p].fa, son = h[p].lson;37 if (p == root){38 root = son, flag = 1;39 h[son].fa = -1;40 }41 else if (son != -1)42 h[fa].lson = son, h[son].fa = fa;43 else h[fa].lson = -1;44 if (!flag)45 while (p != root){46 p = h[p].fa;47 swap(h[p].lson, h[p].rson);48 }49 }50 }51 52 int main(){53 scanf("%d", &n);54 for (int i = 1; i <= n; ++i){55 scanf("%d", &X);56 if (X >= 100) h[X - 100].rson = i, h[i].fa = X - 100;57 else h[X].lson = i, h[i].fa = X;58 }59 60 root = 0;61 work();62 for (int i = 1; i <= n + 1; ++i)63 printf("%d ", ans[i]);64 printf("\n");65 return 0;66 }
(p.s. 我是fa = -1的时候访问了h[fa]，结果RE不止，调到现在才搞明白。。。真是太弱了。。。)
BZOJ1078 [SCOI2008]斜堆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。