「BZOJ2811」[Apio2012] Guard

2015年4月24日7,26112

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一定要放忍者

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K,m,id;
int tag[400005],H[100005],pl[100005],pr[100005];
int top,ql[100005],qr[100005];
int F[100005],G[100005];
struct data{
	int l,r,c;
}a[100005];
vector<pair<int,int> >b;
void modify(int k,int l,int r,int x,int y)
{
	int mid=(l+r)>>1;
	if(x==l&&y==r){tag[k]=1;return;}
	if(x<=mid)modify(k<<1,l,mid,x,min(mid,y));
	if(y>mid)modify(k<<1|1,mid+1,r,max(x,mid+1),y);
}
bool query(int k,int l,int r,int pos)
{
	if(tag[k])return 1;
	int mid=(l+r)>>1;
	if(l==r)return 0;
	if(pos<=mid)return query(k<<1,l,mid,pos);
	else return query(k<<1|1,mid+1,r,pos);
}
int main()
{
	n=read();K=read();m=read();
	for(int i=1;i<=m;i++)
		a[i].l=read(),a[i].r=read(),a[i].c=read();
	for(int i=1;i<=m;i++)
		if(!a[i].c)modify(1,1,n,a[i].l,a[i].r);
	for(int i=1;i<=n;i++)
		if(!query(1,1,n,i))pl[i]=pr[i]=++id,H[id]=i;
	if(id==K)
	{
		for(int i=1;i<=id;i++)printf("%d\n",H[i]);
		return 0;
	}
	for(int i=1;i<=n;i++)if(!pr[i])pr[i]=pr[i-1];
	pl[n+1]=inf;
	for(int i=n;i;i--)if(!pl[i])pl[i]=pl[i+1];
	for(int i=1;i<=m;i++)
		if(a[i].c)
		{
			int l=a[i].l,r=a[i].r;
			l=pl[l];r=pr[r];
			if(l>r)continue;
			b.push_back(make_pair(l,r));
		}
	sort(b.begin(),b.end());
	for(int i=0;i<b.size();i++)
	{
		while(top!=0&&b[i].first>=ql[top]&&b[i].second<=qr[top])top--;
		top++;
		ql[top]=b[i].first;qr[top]=b[i].second;
	}
	int mx=0,mn=inf;
	for(int i=1;i<=top;i++)
		if(ql[i]>mx)F[i]=F[i-1]+1,mx=qr[i];
		else F[i]=F[i-1];
	for(int i=top;i;i--)
		if(qr[i]<mn)G[i]=G[i+1]+1,mn=ql[i];
		else G[i]=G[i+1];
	bool flag=0;
	for(int i=1;i<=top;i++)
	{
		if(F[i]!=F[i-1]+1)continue;
		if(ql[i]==qr[i])
		{
			flag=1;
			printf("%d\n",H[ql[i]]);
		}
		else 
		{
			int x=qr[i]-1,t1=0,t2=top+1;
			int l=1,r=i-1;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(qr[mid]<x)t1=mid,l=mid+1;
				else r=mid-1;
			}
			l=i+1,r=top;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(ql[mid]>x)t2=mid,r=mid-1;
				else l=mid+1;
			}
			if(F[t1]+G[t2]+1>K)
			{
				flag=1;
				printf("%d\n",H[qr[i]]);
			}
		}
	}
    if(!flag)puts("-1");
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,K,m,id;

int tag[400005],H[100005],pl[100005],pr[100005];

int top,ql[100005],qr[100005];

int F[100005],G[100005];

struct data{

int l,r,c;

}a[100005];

vector<pair<int,int> >b;

void modify(int k,int l,int r,int x,int y)

{

int mid=(l+r)>>1;

if(x==l&&y==r){tag[k]=1;return;}

if(x<=mid)modify(k<<1,l,mid,x,min(mid,y));

if(y>mid)modify(k<<1|1,mid+1,r,max(x,mid+1),y);

}

bool query(int k,int l,int r,int pos)

{

if(tag[k])return 1;

int mid=(l+r)>>1;

if(l==r)return 0;

if(pos<=mid)return query(k<<1,l,mid,pos);

else return query(k<<1|1,mid+1,r,pos);

}

int main()

{

n=read();K=read();m=read();

for(int i=1;i<=m;i++)

a[i].l=read(),a[i].r=read(),a[i].c=read();

for(int i=1;i<=m;i++)

if(!a[i].c)modify(1,1,n,a[i].l,a[i].r);

for(int i=1;i<=n;i++)

if(!query(1,1,n,i))pl[i]=pr[i]=++id,H[id]=i;

if(id==K)

{

for(int i=1;i<=id;i++)printf("%d\n",H[i]);

return 0;

}

for(int i=1;i<=n;i++)if(!pr[i])pr[i]=pr[i-1];

pl[n+1]=inf;

for(int i=n;i;i--)if(!pl[i])pl[i]=pl[i+1];

for(int i=1;i<=m;i++)

if(a[i].c)

{

int l=a[i].l,r=a[i].r;

l=pl[l];r=pr[r];

if(l>r)continue;

b.push_back(make_pair(l,r));

}

sort(b.begin(),b.end());

for(int i=0;i<b.size();i++)

{

while(top!=0&&b[i].first>=ql[top]&&b[i].second<=qr[top])top--;

top++;

ql[top]=b[i].first;qr[top]=b[i].second;

}

int mx=0,mn=inf;

for(int i=1;i<=top;i++)

if(ql[i]>mx)F[i]=F[i-1]+1,mx=qr[i];

else F[i]=F[i-1];

for(int i=top;i;i--)

if(qr[i]<mn)G[i]=G[i+1]+1,mn=ql[i];

else G[i]=G[i+1];

bool flag=0;

for(int i=1;i<=top;i++)

{

if(F[i]!=F[i-1]+1)continue;

if(ql[i]==qr[i])

{

flag=1;

printf("%d\n",H[ql[i]]);

}

else

{

int x=qr[i]-1,t1=0,t2=top+1;

int l=1,r=i-1;

while(l<=r)

{

int mid=(l+r)>>1;

if(qr[mid]<x)t1=mid,l=mid+1;

else r=mid-1;

}

l=i+1,r=top;

while(l<=r)

{

int mid=(l+r)>>1;

if(ql[mid]>x)t2=mid,r=mid-1;

else l=mid+1;

}

if(F[t1]+G[t2]+1>K)

{

flag=1;

printf("%d\n",H[qr[i]]);

}

if(!flag)puts("-1");

return 0;

}

« 「BZOJ1095」[ZJOI2007] Hide 捉迷藏「BZOJ3624」[Apio2008] 免费道路 »

233333

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

彳亍者无疆

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

伟安生不解机

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

Gcjh

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

liuyunhui246

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

hzwer

改了。。。

Gcjh

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

罗崚骁

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

陆葳蕤

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

罗崚骁

傻叉

陆葳蕤

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

De℃,.: )

%lwr。。。

hzwer.com _ Home | http://hzwer.com

「BZOJ2811」[Apio2012] Guard

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论