【bzoj2811】[Apio2012]Guard

2015年4月24日2,59012

Description

Input

Output

Sample Input

5 3 4
1 2 1
3 4 1
4 4 0
4 5 1

Sample Output

3
5

HINT

在这个样例中,有两种可能的安排方式:1,3,5 或者 2,3,5。即 3 和 5
后面必然躲着一个忍者。
考虑第一个灌木丛,存在一种安排方案使得它的后面躲着忍者,但也存在一
种安排方案使得它后面没有躲忍者,因此不应该输出 1。同理,不应该输出 2。

题解

首先先将0的区间去除,可以用线段树T T

如果去除0剩下的坐标编号等于忍者数,则所有剩下的坐标都要放忍者

重标号后再将有包含其他区间的区间去除

贪心求出F[i]表示前i个区间的最少要放的忍者数(从左到右没有忍者的区间在右端点放一个),G[i]表示后i个区间。。。

然后依次考虑每个区间,如果它的右端点x需要放一个忍者,考虑能否在x-1放

二分出覆盖x的区间范围l-r

若F[l-1]+G[r+1]+1>K则x一定要放忍者

 

  • 罗崚骁2015年11月1日 下午10:03 回复

    其实预处理可以不用线段树……可以用类似于差分数组的方法……线性时间内就可以算出来而且代码挺短……

    #1  
    • 陆葳蕤2015年11月2日 上午8:32 回复

      %%%%%%%%%%%%%%%%%%%

      #11
      • 罗崚骁2015年11月11日 下午2:56 回复

        傻叉

        #12
        • 陆葳蕤2015年11月11日 下午3:08 回复

          %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

          #13
          • De℃,.: )2015年11月11日 下午7:57

            %lwr。。。

            #14
  • Gcjh2015年11月22日 上午10:47 回复

    好像一组数据卡掉了
    10 1 5
    6 8 0
    5 6 1
    4 6 1
    3 9 1
    7 7 0

    #2  
  • Gcjh2015年11月22日 上午10:48 回复

    top为什么要 > 1, top != 0 应该就可以了吧

    #3  
    • liuyunhui2462016年4月13日 下午10:43 回复

      恩恩。top>1就会有些数据过不了QAQ

      #31
      • hzwer2016年5月1日 下午11:23 回复
        admin

        改了。。。

        #32
  • 伟安生不解机2016年4月13日 下午11:12 回复

    可以解释一下95行x=qr[i]-1而不是x=qr[i]的原因吗?

    #4  
  • 2333332016年4月30日 上午10:31 回复

    代码是错的。国际数据就会挂

    #5  
    • 彳亍者 无疆2016年5月1日 下午3:19 回复

      是不是因为楼下说的那个问题哦QAQ

      #51