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)
{
flag=0;ans=0;num=0;
if(!n&&!k) break;
scanf("%s",s+1);//只要輸入 不用再轉化進一個int數組 否則會超時 所以不必要的操作一定不要要
len=strlen(s+1);
build(1,1,len);
for(i=1;i<=len;i++)
if(s[i]=='0') {flag=1;break;}
if(k==0)
{
if(node[1].num1==len) printf("0\n");
else
printf("-1\n");
continue;
}
if(flag==0) {printf("0\n");continue;}
int pos;//記錄最左邊0的位置
flag=0;
while(pos=query(1))
{
if(pos==-1) break;
left=pos;right=pos+k-1;
if(right>len) {printf("-1\n");flag=1;break;}
update(1,left,right);
ans++;
}
if(flag) continue;
else printf("%d\n",ans);
}
return 0;
}
收獲： 原來一些無用的小操作也能引起超時
另外 那些紅色字體 很重要 以後直接按那種方式寫好了 標准
