【BZOJ2811】[APIO2012] Guard(差分+贪心)

点此看题面

大致题意: 一个长度为\(n\)的序列,其中有\(k\)\(1\)。有\(m\)个限制形如区间\([l,r]\)内是否有\(1\),求哪些位置肯定有\(1\)

前言

\(Jan\ 29th\)刷题计划(4/6),算法标签:贪心。

一开始想简单了,结果自闭了一个多小时,然后去做作业做了半个小时,再翻了翻题解,才发现自己太\(naive\)了。

预处理

首先,对于\(0\)的限制区间,我们可以用差分,标记出序列中不为\(1\)的位置,然后把这些位置删掉。

如果此时剩下的位置个数恰好为\(k\),那么直接把所有位置输出即可。

接下来,对于\(1\)的限制区间,若存在一个大区间覆盖一个小区间,我们就把大区间删去。然后将所有区间排序,则它们的左右端点必然分别都是递增的。

显然,如果一个区间只包含一个位置,即左右端点相等,那么这个位置必然是\(1\)

贪心

然后,我们要考虑的,是那些尚未确定是\(1\)的位置,是否一定是\(1\)

\(Fr_i\)为达成前\(i\)个区间的限制条件至少所需\(1\)的数量,\(Bk_i\)为达成后\(i\)个区间的限制条件至少所需\(1\)的数量。

这可以通过贪心求得。我们按序枚举每一个尚未满足条件的区间,然后尽量选择最远的位置,即另一个端点的位置,放置一个\(1\),这样一来便能求出\(Fr_i\)\(Bk_i\)了。

于是我们枚举那些尚未确定的位置,并设\(S(x)\)表示必须选\(x\)时至少所需\(1\)的数量。

则,如果一个位置\(x\)必须被选,就要满足\(S(x)\le k\),且\(S(x-1)>k\&\&S(x+1)>k\)

这样一来,我们的关键问题就变成了如何求\(S(x)\)

由于所有包含\(x\)的区间在选择了\(x\)的情况下都已经达成了限制,所以我们只要二分出最后一个右端点小于\(x\)的区间\(a\)第一个左端点大于\(x\)的区间\(b\),则\(S(x)=Fr_a+Bk_b+1\)

具体实现详见代码。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LB lower_bound
#define UB upper_bound
using namespace std;
int n,m,k,tot,cnt,p[N+5],w[N+5],Fr[N+5],Bk[N+5];
struct line
{
    int x,y;I line(CI a=0,CI b=0):x(a),y(b){}
    I bool operator < (Con line& o) Con {return x^o.x?x<o.x:y>o.y;}
}s[N+5];
I int S(CI x)//求出在必须选x时至少需要多少个1
{
    RI l,r,mid,t=1;//因为选择了x,所以初始化需要1的个数为1
    l=1,r=tot;W(l<=r) s[mid=l+r>>1].y>=x?r=mid-1:l=mid+1;t+=Fr[l-1];//求出最后一个右端点小于x的区间
    l=1,r=tot;W(l<=r) s[mid=l+r>>1].x<=x?l=mid+1:r=mid-1;t+=Bk[r+1];//求出第一个左端点大于x的区间
    return t;
}
int main()
{
    RI i,t=0,op,x,y;for(scanf("%d%d%d",&n,&k,&m),i=1;i<=m;++i)
        scanf("%d%d%d",&x,&y,&op),op?(s[++t]=line(x,y),0):(++p[x],--p[y+1]);
    for(i=1;i<=n;++i) p[i+1]+=p[i],!p[i]&&(p[++cnt]=i);p[cnt+1]=n+1;//差分,删去肯定不为1的位置
    if(cnt==k) {for(i=1;i<=cnt;++i) printf("%d\n",p[i]);return 0;}//如果当前剩余位置恰好k个
    for(i=1;i<=t;++i) s[i].x=LB(p+1,p+cnt+2,s[i].x)-p,
        s[i].y=UB(p+1,p+cnt+2,s[i].y)-p-1,s[i].x==s[i].y&&(w[s[i].x]=1);//如果左右端点相等,则这个位置必然为1
    for(sort(s+1,s+t+1),i=1;i<=t;++i) {W(tot&&s[tot].y>s[i].y) --tot;s[++tot]=s[i];}//除去包含其他区间的区间
    for(i=1;i<=tot;i=t) {Fr[i]=Fr[i-1]+1,t=i+1;W(t<=tot&&s[t].x<=s[i].y) Fr[t++]=Fr[i];}//贪心求出Fr
    for(i=tot;i>=1;i=t) {Bk[i]=Bk[i+1]+1,t=i-1;W(t>=1&&s[t].y>=s[i].x) Bk[t--]=Bk[i];}//贪心求出Bk
    for(i=1;i<=cnt;++i) !w[i]&&S(i)<=k&&S(i-1)>k&&S(i+1)>k&&(w[i]=1);//枚举判断每一个尚不能确定的位置
    RI fg=0;for(i=1;i<=cnt;++i) w[i]&&(printf("%d\n",p[i]),fg=1);return !fg&&puts("-1"),0;//输出答案
}

【BZOJ2811】[APIO2012] Guard(差分+贪心)

上一篇:深入理解C# 第三版学习笔记


下一篇:* for Windows