HDU 4614 Vases and Flowers 解题报告

题意：有n个花盆，最开始都是空的，有两种操作，第一种从第i个花盆开始，给你k朵花，然你把空的花盆插上花，插到最后还有花，就把花丢掉，（输出开始插的花盆编号和最后一朵花的花盆编号，如果不能插一朵，就输出Can not put any one.

），第二种操作就是从I到J花盆，清除其中的花（输出清除的花数）。

解题思路：线段树的基本操作，解题思路一是线段树+ 二分插的位置，还有一种是直接线段树（利用性质直接查找插花的位置）

解题代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #define MAXN 50005
  5 struct node{
  6    int left ,right , mid ;
  7    int num , cover ;
  8 }tree[MAXN *4];
  9 int L(int c){
 10   return 2 *c ;
 11 }
 12 int R(int c){
 13   return 2 *c + 1;
 14 }
 15 void Pushdown(int c){
 16      if(tree[c].cover == 1){
 17         tree[L(c)].cover = 1;
 18         tree[L(c)].num = 0;
 19         tree[R(c)].cover = 1;
 20         tree[R(c)].num = 0;
 21         tree[c].cover = 2 ;
 22      }
 23      else if(tree[c].cover == 0){
 24         tree[L(c)].cover = 0 ;
 25         tree[R(c)].cover = 0 ;
 26         tree[L(c)].num = (tree[L(c)].right - tree[L(c)].left + 1);
 27         tree[R(c)].num = (tree[R(c)].right - tree[R(c)].left + 1);
 28         tree[c].cover = 2;
 29      }//两种状态，使其跟新后不再跟新
 30 }
 31 void Pushup(int c)
 32 {
 33      tree[c].num = tree[L(c)].num + tree[R(c)].num;
 34 }
 35 void build(int c ,int p , int v ){
 36     tree[c].left = p ;
 37     tree[c].right = v ;
 38     tree[c].mid = (p+v)/2;
 39     tree[c].cover = 0 ;
 40     tree[c].num = 0 ;
 41     if(p == v){
 42       tree[c].num = 1 ;//空花盆为1，这样好查找
 43       return ;
 44     }
 45     build(L(c),p,tree[c].mid);
 46     build(R(c),tree[c].mid+1 ,v);
 47     Pushup(c);
 48 }
 49 int tsum = 0 ;
 50 void getsum(int c , int p ,int v ){
 51     if(p <= tree[c].left && v>= tree[c].right){
 52       tsum += tree[c].num ;
 53       return ;
 54     }
 55     Pushdown(c);
 56     if(v <= tree[c].mid )getsum(L(c),p,v);
 57     else if(p > tree[c].mid)  getsum(R(c),p,v);
 58     else {
 59      getsum(L(c),p,tree[c].mid);
 60      getsum(R(c),tree[c].mid + 1,v);
 61     }
 62 }
 63 void update(int c , int p , int v , int value){
 64   //    printf("%d %d
",p,v);
 65     if (p <= tree[c].left  && v >= tree[c].right){
 66        tree[c].num = (tree[c].right - tree[c].left + 1) * (1-value);
 67        tree[c].cover = value;
 68        return ;
 69     }
 70     Pushdown(c);
 71     if(v <= tree[c].mid ) update(L(c),p , v ,value);
 72     else if(p > tree[c].mid) update(R(c),p,v,value);
 73     else {
 74        update(L(c),p,tree[c].mid,value);
 75        update(R(c),tree[c].mid +1 ,v,value);
 76     }
 77     Pushup(c);
 78 }
 79 int ok = 0 ;
 80 void Find(int c ,int value){
 81    if(tree[c].left == tree[c].right)
 82    {
 83      ok = tree[c].left;
 84      return;
 85    }
 86    Pushdown(c);
 87    if(tree[L(c)].num < value )
 88      Find(R(c),value - tree[L(c)].num);
 89    else Find(L(c),value);
 90 }
 91 
 92 int main(){
 93   int t ;
 94   scanf("%d",&t);
 95   while(t--){
 96     int n , m ;
 97     scanf("%d %d",&n,&m);
 98     build(1,1,n);
 99     for(int i = 1;i <= m;i ++){
100 
101       int t1,t2,t3;
102       scanf("%d %d %d",&t1,&t2,&t3);
103       if(t1 == 2){
104          t2++;
105          t3++;
106          tsum = 0;
107          getsum(1,t2,t3);
108          update(1,t2,t3,0);
109          printf("%d
",(t3-t2+1)-tsum);
110       }else {
111         t2++;
112         tsum = 0 ;
113         int ok1 = 0 ;
114         if(t2 != 1)
115            getsum(1,1,t2-1);
116         if(tsum == tree[1].num)
117             printf("Can not put any one.
");
118         else {
119             Find(1,tsum+1);
120             ok1 = ok ;
121             if(tree[1].num - tsum < t3 )
122                 Find(1,tree[1].num);
123             else Find(1,tsum + t3);
124             update(1,ok1,ok,1);
125 
126             printf("%d %d
",ok1-1,ok-1);
127         }
128 
129 
130       }
131     }
132    
133      printf("
");
134   }
135   return 0 ;
136 }

View Code

没有梦想，何谈远方