首页 > 代码库 > hdu--3275--线段树<again>
hdu--3275--线段树<again>
又加强了 对线段树 延迟标记的理解~~
题意很简单 给你一串数字01组成. 每次必须操作K个数 将其翻转 即0->1 1->0 就相当 对于一段区间 [ L , L+K-1 ] 的0和1的数量 进行swap操作
首先 解这题 一点必须想到 求最少操作次数 肯定是从最左边开始.
那么我每次 query(find)操作 查找到最左边的0的位置 如果不存在就返回-1 表示 全是1了
然后对这个[ pos , pos+k-1 ]进行翻转操作 这边有个判断 就是如果 pos+k-1 > n的话 就相当于无法成功通过翻转实现全部1的结果了
注意下 pushDown 和 pushUp函数的使用及函数体内容.... 这些都是 精华啊 值得去理解~ 而且我也讲不明白..
1 //0代表灯笼是暗的 1代表灯笼是亮的 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 100010; 7 char str[size]; 8 struct data 9 { 10 int L; 11 int R; 12 int flag; 13 int numOne , numZero; 14 }tree[size*4]; 15 16 void pushUp( int root ) 17 { 18 tree[root].numOne = tree[root<<1].numOne + tree[root<<1|1].numOne; 19 tree[root].numZero = tree[root<<1].numZero + tree[root<<1|1].numZero; 20 } 21 22 void pushDown( int root ) 23 { 24 tree[root<<1].flag ^= 1; 25 tree[root<<1|1].flag ^= 1; 26 swap( tree[root<<1].numZero , tree[root<<1].numOne ); 27 swap( tree[root<<1|1].numZero , tree[root<<1|1].numOne ); 28 } 29 30 void build( int root , int L , int R ) 31 { 32 int Mid = ( L + R ) >> 1; 33 tree[root].L = L; 34 tree[root].R = R; 35 tree[root].flag = 0; 36 if( L==R ) 37 { 38 if( str[L]==‘1‘ ) 39 { 40 tree[root].numOne = 1; 41 tree[root].numZero = 0; 42 } 43 else 44 { 45 tree[root].numOne = 0; 46 tree[root].numZero = 1; 47 } 48 return ; 49 } 50 build( root<<1 , L , Mid ); 51 build( root<<1|1 , Mid+1 , R ); 52 pushUp( root ); 53 } 54 55 void update( int root , int L , int R ) 56 { 57 int Mid = ( tree[root].L + tree[root].R ) >> 1; 58 if( tree[root].L == L && tree[root].R == R ) 59 { 60 swap( tree[root].numZero , tree[root].numOne ); 61 tree[root].flag ^= 1; 62 return ; 63 } 64 if( tree[root].flag ) 65 { 66 pushDown( root ); 67 tree[root].flag = 0; 68 } 69 if( R<=Mid ) 70 update( root<<1 , L , R ); 71 else if( L>=Mid+1 ) 72 update( root<<1|1 , L , R ); 73 else 74 { 75 update( root<<1 , L , Mid ); 76 update( root<<1|1 , Mid+1 , R ); 77 } 78 pushUp( root ); 79 } 80 81 int query( int root ) 82 { 83 int ans = -1; 84 if( tree[root].L == tree[root].R ) 85 { 86 return tree[root].L; 87 } 88 if( tree[root].flag ) 89 { 90 pushDown( root ); 91 tree[root].flag = 0; 92 } 93 if( tree[root<<1].numZero ) 94 ans = query( root<<1 ); 95 else if( tree[root<<1|1].numZero ) 96 ans = query( root<<1|1 ); 97 return ans; 98 } 99 100 int main()101 {102 cin.sync_with_stdio(false);103 int n , k , cnt , pos;104 bool flag;105 while( cin >> n >> k && ( n||k ) )106 {107 cnt = 0;108 flag = true;109 cin >> (str+1);110 build( 1 , 1 , n );111 if( tree[1].numOne == n )112 {113 cout << 0 << endl;114 }115 else if( !k )116 {117 cout << -1 << endl;118 }119 else120 {121 while(1)122 {123 pos = query( 1 );124 if( pos == -1 )125 break;126 if( pos+k-1>n )127 {128 flag = false;129 break;130 } 131 update( 1 , pos , pos+k-1 );132 ++ cnt;133 }134 if( flag )135 cout << cnt << endl;136 else137 cout << -1 << endl;138 }139 }140 return 0;141 }
today:
小孩子才问你为什么不理我了
是不是不喜欢我了
成年人都是默契地相互疏远
hdu--3275--线段树<again>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。