算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

   给一个长度为N(N<10,000)的数列,每次选取值最小的元素并翻转前面的数列,然后删除这个元素。请在每次操作之前输出这个最小元素的位置。

吐槽:

    1. 很好的splay热身题,强势推荐....
    2. 自底向上的维护对于懒惰标记的向下传递好像很无力? NO! 写过zkw版线段树么.... 看我之前写过的一篇题解吧! 自底向上同样可以传递懒惰标记。

算法分析:

    这里的splay应用是... 放弃了元素之间的优先级,完全模拟一个数组(像笛卡尔树那样)
    要解决一些问题:
        1. 如何查找元素最小的元素? 记录最小值? NO! 数列的数组下标和splay的下标是一样的!!!!
        2. 如何翻转一个区间? 先把这个区间“抽”出来,然后在这个区间的代表节点上加一个标记,传递标记的时候就旋转左右子树。
        3. 如何删除节点? 找到节点的前驱与后继,然后通过splay前驱与后继把这个节点“抽”出来。
        4. 如何在向上splay的时候传递懒惰标记? 看我之前一篇题解吧! 在splay之前更新所有的父亲节点!
    HDU代码长度第三 ~~ 继续figo的传统
 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<cassert>
 4 using namespace std;
 5 const int N = 100005;
 6 int n,splsize;
 7 struct node{
 8     int flag,sz,ch[2],p;
 9 } tree[N];
10 struct sample{
11     int id,v;
12     bool operator < (sample A) const{
13         return A.v == v ? id < A.id : v < A.v;
14     }
15 }num[N];
16 // splay
17 inline void upt(int x){
18     tree[x].sz = tree[tree[x].ch[0]].sz + tree[tree[x].ch[1]].sz+1;
19 }
20 inline void setchd(int y,int x,int p){
21     tree[y].ch[p] = x; tree[x].p = y;
22 }
23 void rot(int x){
24     int y = tree[x].p;
25     int chd = tree[y].ch[1] == x;
26     setchd(tree[y].p,x,tree[tree[y].p].ch[1] == y);
27     setchd(y,tree[x].ch[chd^1],chd);
28     setchd(x,y,chd^1);
29     upt(y);  upt(x);
30 }
31 void pushup(int x){
32     if(tree[x].flag) {
33         tree[x].flag=0;
34         swap(tree[x].ch[0],tree[x].ch[1]);
35         tree[tree[x].ch[0]].flag ^= 1;
36         tree[tree[x].ch[1]].flag ^= 1;
37     }
38 }
39 void dfs(int x){
40     if(!x) return ;
41     dfs(tree[x].p);
42     pushup(x);
43 }
44 void splay(int x,int rt){
45     dfs(x);
46     while(tree[x].p!=rt){
47         int y = tree[x].p;
48         int flag = tree[y].ch[1] == x;
49         if(tree[tree[x].p].p !=rt && flag == (tree[tree[y].p].ch[1] == y)) rot(y);
50         rot(x);
51     }
52 }
53 // function
54 void ins(int x){
55     setchd(x-1,x,1);
56     tree[x].ch[0] = tree[x].ch[1] = tree[x].flag= 0;
57     splay(x,0);
58 }
59 int cal(int x){
60     splay(x,0);
61     int ans = tree[tree[x].ch[0]].sz +1;
62     tree[tree[x].ch[0]].flag ^=1;
63     int u = tree[x].ch[0];
64     int v = tree[x].ch[1];
65     if(u==0) setchd(0,v,1);
66     else if(v==0) setchd(0,u,1);
67     else {
68         pushup(u); pushup(v);
69         while(tree[u].ch[1]){ u = tree[u].ch[1]; pushup(u);}
70         while(tree[v].ch[0]){ v = tree[v].ch[0]; pushup(v);}
71         splay(u,0);     splay(v,u); 
72         assert(tree[v].ch[0] == x);
73         tree[v].ch[0] = 0;
74     }
75     return ans;
76 }
77 // main
78 int main(){
79     tree[0].ch[0] = tree[0].ch[1] = tree[0].p = 0;
80     while(~scanf("%d",&n) && n){
81         for(int i=0; i<n; i++){
82             scanf("%d",&num[i].v);
83             ins(i+1);
84             num[i].id = i;
85         }
86         sort(num,num+n);
87         for(int i=0; i<n; i++){
88             int pos = num[i].id + 1;
89             int ans = cal(pos) + i;
90             if(i) printf(" ");
91             printf("%d",ans);
92         }
93         puts("");
94     }
95 }
96 
posted on 2012-05-10 20:54 西月弦 阅读(1153) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理