题解：AT_arc190_a [ARC190A] Inside or Outside

赛时没有思路，但同机房的lbr巨佬一眼秒

首先，作为第一题，且赛时有人速通，再加上表意不明的题面，可知本题应为诈骗题。

可以手玩一下小样例或打表。然后可以发现一些性质：

答案不会超过3（可证）
答案为3的情况比较少

由此，我们可以大胆的分类讨论

考虑有解：

答案为1，当且仅当存在一个区间，为 $[1,n]$
答案为2，可以是两个区间都执行2操作，当且仅当存在两个区间无公共点；可以是两个区间，分别执行1,2两个操作，当且仅当存在两个区间，满足其中一个区间能包含另一个区间，此时被包含的区间执行2操作，包含的区间执行1操作；可以是两个区间都执行1操作，当且仅当存在两个区间，相交且一个区间左端点为 $1$ ，一个区间右端点为 $n$ 。
答案为三，当且仅当 $m>=3$ 。

除去这三种情况，就可以直接输出

-1

了。

下面考虑答案为什么不会超过3

显然，除去答案为1,2的情况，一定满足这

m

个区间有至少一个公共点，且两两之间无包含与被包含关系，由此可以将这些区间以左端点为关键字排序，右端点也一定是有序的，这时直接取前三个区间

[l_1,r_1],[l_2,r_2],[l_3,r_3](l_1<l_2<l_3,r_1<r_2<r_3)

，可将1、3两个区间执行1操作，2区间执行2操作即可。

CPP

/*胡金梁*/
#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
inline int read()
{
	int f=1,re=0;
	char ch=getchar();
	while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar();}
	while( isdigit(ch)) re=(re<<3)+(re<<1)+(ch^'0'),ch=getchar();
	return re*f;
}
struct node
{
	int l,r,id;
	bool operator <(const node &t) const
	{
		return (l==t.l?r>t.r:l<t.l);
	}
}q[200005];
signed main()
{
#if __MY_TEST__
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		q[i].l=read(),q[i].r=read();q[i].id=i;
		if(q[i].l==1&&q[i].r==n)
		{
			cout<<1<<endl;
			for(int j=1;j<i;j++) cout<<0<<" ";
			cout<<1<<" ";
			for(int j=i+1;j<=m;j++) cout<<0<<" ";
			return 0; 
		}
	}
	sort(q+1,q+m+1);
	int rmax=q[1].r,rnum=q[1].id;
	for(int i=2;i<=m;i++)
	{
		if(q[i].r<=rmax)
		{
		//	cout<<q[i].l<<" "<<q[i].r<<" "<<rmax<<" "<<rnum<<endl;
			cout<<2<<endl;
			for(int j=1;j<min(rnum,q[i].id);j++)
			{
				cout<<0<<" ";
			}
			if(q[i].id<=rnum)
				cout<<2<<" ";
			else
				cout<<1<<" "; 
			for(int j=min(rnum,q[i].id)+1;j<max(q[i].id,rnum);j++)
			{
				cout<<0<<" ";
			}
			if(q[i].id<=rnum)
				cout<<1<<" ";
			else
				cout<<2<<" "; 
			for(int j=max(q[i].id,rnum)+1;j<=m;j++)
			{
				cout<<0<<" ";
			}
			return 0;
		}
		if(q[i].r>rmax) rmax=q[i].r,rnum=q[i].id;
	}
	int rmin=q[1].r;
	rnum=q[1].id;
	for(int i=2;i<=m;i++)
	{
		if(q[i].l>rmin)
		{
			cout<<2<<endl;
			for(int j=1;j<min(rnum,q[i].id);j++)
			{
				cout<<0<<" ";
			}
			cout<<2<<" ";
			for(int j=min(rnum,q[i].id)+1;j<max(q[i].id,rnum);j++)
			{
				cout<<0<<" ";
			}
			cout<<2<<" ";
			for(int j=max(q[i].id,rnum)+1;j<=m;j++)
			{
				cout<<0<<" ";
			}
			return 0;
		}
		if(q[i].r<rmin) rmin=q[i].r,rnum=q[i].id;
	}
	bool x1=0,x2=0;
	int i1,i2;
	for(int i=1;i<=m;i++)
	{
		if(q[i].l==1)
		{
			x1=1;
			i1=q[i].id;
		}
		if(q[i].r==n)
		{
			x2=1;
			i2=q[i].id;
		}
	}
	if(x1&&x2)
	{
		cout<<2<<endl; 
		for(int i=1;i<min(i1,i2);i++) cout<<"0 ";
		cout<<"1 ";
		for(int i=min(i1,i2)+1;i<max(i1,i2);i++) cout<<"0 ";
		cout<<"1 ";
		for(int i=max(i1,i2)+1;i<=m;i++) cout<<"0 ";
		return 0;
	}
	if(m>=3)
	{
	    cout<<3<<endl;
	    for(int i=1;i<min(min(q[1].id,q[2].id),q[3].id);i++) cout<<"0 ";
	    if(q[1].id==min(min(q[1].id,q[2].id),q[3].id)||q[3].id==min(min(q[1].id,q[2].id),q[3].id)) cout<<"1 ";
	    else cout<<"2 ";
	    for(int i=min(min(q[1].id,q[2].id),q[3].id)+1;i<q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id);i++) cout<<"0 ";
	    if(q[1].id==q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id)||q[3].id==q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id)) cout<<"1 ";
	    else cout<<"2 ";
		for(int i=q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id)+1;i<max(max(q[1].id,q[2].id),q[3].id);i++) cout<<"0 ";
	    if(q[1].id==max(max(q[1].id,q[2].id),q[3].id)||q[3].id==max(max(q[1].id,q[2].id),q[3].id)) cout<<"1 ";
	    else cout<<"2 ";
	    for(int i=max(max(q[1].id,q[2].id),q[3].id)+1;i<=m;i++) cout<<"0 ";
	    return 0;
	}
    cout<<-1<<endl;
    return 0;
}

题解：AT_arc190_a [ARC190A] Inside or Outside

文章操作

相关推荐

评论

题解：AT_arc190_a [ARC190A] Inside or Outside