题解 P5090 【[eJOI2018]互素树】

· · 题解

注：此做法亦可通过 加强版。并且在加强版中表现得更加优秀。

（为了水估值，我也会把这个做法发到加强版中）

既然是个提答，通常不会有什么复杂度正经的做法，多半是考验乱搞能力。

（不过这题好像 xtq 等大佬交了 cpp 文件就跑过去了，我不得不%%%。）

核心思想：随机化 + 贪心

随机化：

随机出来一个排列，即把每个要填的数随出来个优先级，优先级较高的优先考虑。

直接每次 random_shuffle 即可。

贪心：

从根（可以自己规定，也可以随机）出发，dfs 一遍树，每个节点填入剩下的数中与父亲节点互质且优先级最高的数。

用 set 维护剩余的数即可。

根据以上两条就足以通过此题了 ^_^ 。

我就放下代码吧。

code:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define N 100010
int T,n,x[N],y[N],p[N],ans[N],mn,tot,tmp[N];
set<int> s;
inline int _gcd(int a,int b){
    if(b==0)return a;
    return _gcd(b,a%b);
}
vector<int> G[N];
void dfs(int u,int fa){
    for(auto i:s){
        if(!fa||_gcd(tmp[fa],p[i])==1){
            tmp[u]=p[i],s.erase(s.find(i));
            break;
        }
    }
    if(!tmp[u]){
        ++tot;
        tmp[u]=p[(*s.begin())];
        s.erase(s.begin());
    }
    for(auto v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
}
int main(){
    freopen("x.in","r",stdin);
    freopen("x.out","w",stdout);
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;++i)G[i].clear(),p[i]=i;
        for(int i=1;i<n;++i){
            int u=read(),v=read();
            G[u].push_back(v),G[v].push_back(u);
        }
        mn=n;
        for(int Test=1;;++Test){
            s.clear();
            random_shuffle(p+1,p+n+1);
            for(int i=1;i<=n;++i)tmp[i]=0,s.insert(i);
            tot=0;
            dfs(1,0);
            if(tot<mn){
                mn=tot;
                for(int i=1;i<=n;++i){
                    ans[i]=tmp[i];
                }
            }
            if(!mn)break;
        }
        for(int i=1;i<=n;++i){
            printf("%d ",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

如果没有耐心，那么随便跑跑即可获得 95+ 的高分。（测试点 1\sim 6 可以秒出。）

如果有一点耐心，用不到 30min 即可得到 100 分。

在加强版中就更加优秀了，最后一个点不到 1min 就跑完了。有图为证：

因为是个提答，并且我比较懒，所以到这里我就结束了。

其实还有非常多可以优化的地方。（其实这种题目就是仁者见仁，智者见智嘛。）

举个例子吧：把节点按度数排序，度数大的放上大质数。

当然，做完后也不妨思考一下有木有多项式复杂度的解法。

Froggy's blog

呱!!