论静态查错的重要性。。。乱搞题真难调
首先这题看起来就是要分治检验了。
考虑对于区间[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[110000];int len,last[110000]; 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=0; for(int x=p,q=0;x<=r;x++,q++,q%=pL) { int k=last[x]; if(k==0||a[k].y!=l+q) { if(a[k].y==l)return x; else return -1; } else if(a[k].next!=0&&a[a[k].next].y<p)flag=-1; } return flag; } bool divi(int l,int r) { if(l==r)return true; for(int x=l;x<=r;x++) while(last[x]!=0&&a[last[x]].y<l)last[x]=a[last[x]].next; if(l+1==r) if(last[r]!=0&&a[last[r]].y==l&&a[last[r]].next==0)return true; int p=-1,L=r-l+1; for(int x=r-1;x>l;x--) if(last[x]!=0&&a[last[x]].y==l&&(x-l)*2<=L){p=x;break;} int x=p; if(x==-1)return false; int z=check(x,l,r); if(z==0) { if(divi(l,p-1)&&divi(p,r))return true; } else if(z!=-1) { if(z-x>x-l)return false; int u=l+(z-x); if(check(u,l,r)==0&&divi(l,u-1)&&divi(u,r))return true; } return false; } struct edge{int x,y;}e[110000]; 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=1;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 ");continue;} sort(e+1,e+m+1,cmp); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++)ins(e[i].y,e[i].x); if(divi(0,n-1))printf("YES "); else printf("NO "); } return 0; }