自动搬运

查看原文

来自洛谷，原作者为

	_Sein 一尺之棰，日取其半，万世不竭

搬运于2025-08-24 21:59:37，当前版本为作者最后更新于2020-03-21 10:39:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意就给人一种分治的感觉，把联通块合并。

不妨先对给定的边进行处理，把$x>y$的情况交换一下($x<y$也行，不过要另进行讨论了)。

对于$y$，所有没有用到的边$(x_i,y)$，对于当前递归到的状态，产生贡献的一定是$\min\{x_i\}$

因为由于递归的性质，当前进行的就是最晚的。

反证一下也可以，如果不是$\min\{x_i\}$在当前状态放置，那么它先于一部分的$x_i$与$y$相连，但明显$G$图的编号是连续的，那么也就违背了题意，所以不成立。

因此只要统计出所有的$y$的最小$x_i$即可，这些是对于当前递归状态有贡献的。

引理:如果状态是合法的，其必然存在$siz$，使得$G_1$大小为$siz$，$G_2$大小为$n-siz$，$G_1$与$G_2$的并集恰好是当前状态，且$siz$是唯一的。

证明:由于$[0,siz)$与$[siz,2*siz),[2*siz,3*siz),\cdots$分别对应连边，连续的循环区间大小为$siz$，如果$siz$往左偏移，或往右偏移，都会导致区间不再循环。

处理好$siz$之后，断去两个联通块之间的连边，再当成子问题进行处理。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=1e5+5,M=1e6;
template<class o>
inline void qr(o &x)
{
	x=0;char c=gc;
	while(c<'0'||c>'9')c=gc;
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
	if(x/10)qw(x/10);
	putchar(x%10+48);
}
struct edge
{
	int x,y;
	edge(int x=0,int y=0):x(x),y(y){}
	bool operator <(const edge a)const{return x==a.x?y<a.y:x<a.x;}
}a[N];
int L[N];bool v[N];//????????????? 
bool check(int n,int l,int r)
{
	if(n==1)return l==r;
	if(l==r)return 0;
	for(int i=0;i<n;i++)v[i]=0,L[i]=M;
	for(int i=l;i<r;i++)
	{
		int x=a[i].x,y=a[i].y;
		if(L[y]==x)return 0;
		L[y]=min(L[y],x); 
	}
	for(int i=0;i<n;i++)
		if(L[i]==0)v[i]=1;
		else if(L[i]==L[i-1]+1&&v[i-1])v[i]=1; 
	int siz;bool bk;
	for(int i=0;i<n/2;i++)
	{
		siz=i+1;bk=1;
		for(int j=i+siz;j<n;j+=siz)
		{
			if(L[j]==i&&v[j])continue;
			bk=0;break;
		}
		if(bk)break;
	}
	if(!bk)return 0;
	int p1=0,p2=0,i;
	for(i=l;i<r;i++)
	{
		int x=a[i].x,y=a[i].y;
		if(x==siz)break;
		if(y>=siz&&y%siz!=x) return 0;
		if(y>=siz)continue;
		a[p1++]=edge(x,y);
	}p2=p1;
	for(;i<r;i++)
	{
		int x=a[i].x,y=a[i].y;
		a[p2++]=edge(x-siz,y-siz);
	}
	return check(siz,0,p1)&&check(n-siz,p1,p2);
}
int main()
{
	int T;qr(T);
	while(T--)
	{
		int n,m;qr(n),qr(m);
		for(int i=0,x,y;i<m;i++){qr(x),qr(y);if(x>y)swap(x,y);a[i]=edge(x,y);}
		sort(a,a+m);
		if(check(n,0,m))puts("YES");
		else puts("NO");
	}
	return 0;
}