BZOJ5200: [NWERC2017]Factor-Free Tree【暴力+启发式分裂】

5200: [NWERC2017]Factor-Free Tree

【题目描述】

传送门

【题解】

这里有log_2(a)筛单个数的素数的方法,只要在欧拉筛上加点东西就可以了。

然后接下来就是暴力DFS+启发式分裂,复杂度O(Nlog_2(N))

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1000005,MAXL=10000005;
int n,Top,m,a[MAXN],L[MAXN],R[MAXN],F[MAXN],Hsh[MAXL],p[MAXL],pre[MAXL];
char OUT[MAXN*8];
#include<cctype>
char nc(){
    static char buf[100000],*L=buf,*R=buf;
    return (L==R&&(R=(L=buf)+fread(buf,1,100000,stdin)),L==R)?EOF:*L++;
}
int read(){
    int ret=0;char ch=nc();bool f=1;
    for(;!isdigit(ch);ch=nc()) f^=!(ch^'-');
    for(; isdigit(ch);ch=nc()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
void make_p(int Len){
    for(int i=2;i<=Len;i++){
        if(!pre[i]) p[++p[0]]=i,pre[i]=i;
        for(int j=1;j<=p[0]&&p[j]*i<=Len;j++){
            pre[p[j]*i]=pre[i];
            if(i%p[j]==0) break;
        }
    }
}
bool DFS(int Lt,int Rt,int Fa){
    if(Lt>Rt) return 1;
    int l=Lt,r=Rt;
    while(l<=r){
        if(L[l]<Lt&&R[l]>Rt){F[l]=Fa;return DFS(Lt,l-1,l)&&DFS(l+1,Rt,l);}
        if(L[r]<Lt&&R[r]>Rt){F[r]=Fa;return DFS(Lt,r-1,r)&&DFS(r+1,Rt,r);}
        l++,r--;
    }
    return 0;
}
void print(int x){if(x>=10) print(x/10);OUT[++Top]=x%10+48;}
int main(){
    n=read();make_p(10000000);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){
        int ID=0,x=a[i];
        while(x>1){
            int W=pre[x];
            ID=max(Hsh[W],ID),Hsh[W]=i;
            while(x%W==0&&x>1) x/=W;
        }
        L[i]=ID;
    }
    memset(Hsh,63,sizeof(Hsh));
    for(int i=n;i;i--){
        int ID=n+1,x=a[i];
        while(x>1){
            int W=pre[x];
            ID=min(Hsh[W],ID),Hsh[W]=i;
            while(x%W==0&&x>1) x/=W;
        }
        R[i]=ID;
    }
    if(!DFS(1,n,0)) return printf("impossible\n"),0;
    Top=-1;
    for(int i=1;i<=n;i++) print(F[i]),OUT[++Top]=(i==n?'\n':' ');
    fwrite(OUT,1,Top,stdout);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部