hdu3275 Light很好很好的线段树收获丰富
Light
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 707 Accepted Submission(s): 224
Problem Description
Felicia was given a long string of fancy lanterns, but not all of them are on to light the night. Felicia felt bad about that and he wants to light up all the lanterns. There is a kind of magic switch which can change the states of k continuous lanterns. Once you choose k continuous lanterns and install a switch on them, the states of all k continuous lanterns can be changed together (on ->off or off ->on), but you cannot choose some ones be changed and some ones not be changed.
Felicia wants to buy as few switches as possible so that he can install them to turn on all the lanterns. Please notice that each switch must control exactly k continuous lanterns.
Input
The input consists of multiple test cases. The first line of each case contains integers n(0 < n <= 100000), which is the length of that string of fancy lanterns, and k(0 <= k <= n), which is the number of continuous lanterns that a switch will control. The next line consists of a string of “01” with length n. “1” means that lantern is on and “0” means off. Your job is turn all the “0” to “1”.
The last test case is followed by a line containing two zeros.
Output
If you cannot finish this job, output “-1” or you should output the minimum number switches that you should buy to turn on all the lanterns.
Sample Input
4 2
0000
4 2
1001
4 2
0110
4 2
0111
0 0
Sample Output
2
1
3
-1
题意：
输入n k
以及n个0或1
问把串全部转化为1 每步会把从pos开始的第k个全部更改为相反的状态 至少需要多少步 如果无法全部变为1 则输-1
思路： 写几组数据可以发现 从左往右遇到0就变为1 到最后全变为1 这样得出的就是最少的步骤
关键是如何迅速的找出有0的位置 这时候就要用线段树去标记一个段内是否有0了
[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct haha
{
int num1;
int num0;
int flag;
int left;
int right;
}node[100000*4];
char s[100000+100];
void build(int nd,int left,int right)
{
node[nd].left=left;
node[nd].right=right;
node[nd].flag=0;
if(node[nd].left==node[nd].right)
{
if(s[node[nd].left]=='1')
{
node[nd].num0=0;
node[nd].num1=1;
}
else
{
node[nd].num1=0;
node[nd].num0=1;
}
return ;
}
int mid=(left+right)/2;
build(nd*2,left,mid);
build(nd*2+1,mid+1,right);
node[nd].num0=node[nd*2].num0+node[nd*2+1].num0;
node[nd].num1=node[nd*2].num1+node[nd*2+1].num1;
}
void change(int nd)
{
int temp;
if(node[nd].left==node[nd].right) return ;
temp=node[nd*2].num0;node[nd*2].num0=node[nd*2].num1;node[nd*2].num1=temp;
temp=node[nd*2+1].num0;node[nd*2+1].num0=node[nd*2+1].num1;node[nd*2+1].num1=temp;
<span style="color:#FF0000;"> // node[nd].flag=0;node[nd*2].flag=1;node[nd*2+1].flag=1;//这样写是绝对错误的 因为这里 我错了10几遍啊 呜呜
node[nd].flag=!node[nd].flag;node[nd*2].flag=!node[nd*2].flag;//应该这样写 注意 以后都要这样规范的写
node[nd*2+1].flag=!node[nd*2+1].flag;//因为你不能保证一个不被标记2边 即子节点可能标记2边 </span>
}
int query(int nd)
{
if(node[nd].left==node[nd].right) return node[nd].left;//==写成了= 一个劲的错 呜呜
if(node[nd].flag) change(nd);
int pos=-1;
if(node[nd*2].num0) pos=query(nd*2);
else
if(node[nd*2+1].num0) pos=query(nd*2+1);
node[nd].num0=node[nd*2].num0+node[nd*2+1].num0;
node[nd].num1=node[nd*2].num1+node[nd*2+1].num1;
return pos;
}
void update(int nd,int left,int right)
{
int i,j,mid;
if(node[nd].flag) change(nd);
if(node[nd].left==left&&node[nd].right==right)
{
int temp;
temp=node[nd].num0;node[nd].num0=node[nd].num1;node[nd].num1=temp;
node[nd].flag=1;
return ;
}
mid=(node[nd].left+node[nd].right)/2;
if(right<=mid) update(nd*2,left,right);
else if(left>mid) update(nd*2+1,left,right);
else
{
update(nd*2,left,mid);
update(nd*2+1,mid+1,right);
}
node[nd].num0=node[nd*2].num0+node[nd*2+1].num0;
node[nd].num1=node[nd*2].num1+node[nd*2+1].num1;
return ;
}
int main()
{
int n,k,i,j,flag,left,right,ans,num,len;
while(scanf("%d %d",&n,&k)!=EOF)
{&n
补充：软件开发 , C++ ,
