首页 > ACM题库 > HDU-杭电 > HDU 3275-Light-线段树-[解题报告]HOJ
2014
03-13

HDU 3275-Light-线段树-[解题报告]HOJ

Light

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

4 2
0000
4 2
1001
4 2
0110
4 2
0111
0 0

样例输出:

2
1
3
-1

#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;
     //  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边 

}
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;
}

参考:http://blog.csdn.net/hnust_xiehonghao/article/details/7931909


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。