论静态查错的重要性。。。乱搞题真难调
首先这题看起来就是要分治检验了。
考虑对于区间[l,r],分成[l,p-1]和[p,r]使得这两个区间合并可以得到[l,r],并且要保证后面一个区间较大
设前一个区间长度为pL,合法只有i∈[p,r],i和(i-p)%pL有一条边,并且(i-p)%pL是i第一个连向的区间里面的点,并且i连向的第二个点不能<p
维护一个排过序的邻接表,last数组表示在当前区间内第x个点指向的第1个点,对于前两个条件,我们可以理解为找一个长度pL,假设<=l+pL-1的点都指向自己,那么整个区间的指向构成一个l~l+pL-1的循环
而对于当前区间分割,l一定是归于左边的
把所有和l右边的代入验证是一个基本的思路,但其实我们试两次就够了
考虑对于区间[l,(r-l+1)/2]指向l的最后一个点p,如果要分割,它一定是要归到右区间的
此时我们先找出它进行一次验证,当验证到某个点失配的时候跳出,假设这个点为u
不难发现,只有匹配长度没有超过pL,才有可能有另外的方案,否则循环节的长度已经被确定了,此时我们知道:[p,u-1]和[l,l+u-1-p]是匹配的,而到达u开始失配,那么u只能指向l构成循环节,才有合法的可能
那么通过p和u就确定了循环节长度,我们只需要验证l+u-p即可
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>using namespace std;struct node
{
int x,y,next;
}a[];int len,last[];
void ins(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
int check(int p,int l,int r)
{
int pL=p-l,flag=;
for(int x=p,q=;x<=r;x++,q++,q%=pL)
{
int k=last[x];
if(k==||a[k].y!=l+q)
{
if(a[k].y==l)return x;
else return -;
}
else if(a[k].next!=&&a[a[k].next].y<p)flag=-;
}
return flag;
}
bool divi(int l,int r)
{
if(l==r)return true;
for(int x=l;x<=r;x++)
while(last[x]!=&&a[last[x]].y<l)last[x]=a[last[x]].next;
if(l+==r)
if(last[r]!=&&a[last[r]].y==l&&a[last[r]].next==)return true; int p=-,L=r-l+;
for(int x=r-;x>l;x--)
if(last[x]!=&&a[last[x]].y==l&&(x-l)*<=L){p=x;break;}
int x=p;
if(x==-)return false; int z=check(x,l,r);
if(z==)
{
if(divi(l,p-)&&divi(p,r))return true;
}
else if(z!=-)
{
if(z-x>x-l)return false;
int u=l+(z-x);
if(check(u,l,r)==&&divi(l,u-)&&divi(u,r))return true;
}
return false;
}struct edge{int x,y;}e[];
bool cmp(edge e1,edge e2){return e1.x>e2.x;}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
int n,m; bool bk=true;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&e[i].x,&e[i].y);
if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
if(e[i].x==e[i].y)bk=false;
}
if(bk==false){printf("NO\n");continue;} sort(e+,e+m+,cmp);
len=;memset(last,,sizeof(last));
for(int i=;i<=m;i++)ins(e[i].y,e[i].x);
if(divi(,n-))printf("YES\n");
else printf("NO\n");
} return ;
}