题解 P4386 【[SHOI2015]零件组装机】

· · 题解

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

不妨先对给定的边进行处理，把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;
}