题解 P5830 [ZJOI2016]随机树生成器

wishapig · 2021-12-23 11:26:07 · 题解

题目大意：

给出 4 种随机生成树的方式，然后有 m 组询问，每次给出一棵大小为 1000 的树，问是用哪种方式生成的。

这题很有趣啊，就是个概率统计题嘛。

首先四种树的生成方法决定了生成出来的树一定是有一些特征的，但像我这种数学不好的人当然是不会概率分析的啦，那怎么办呢？

就像在正方形里随机撒点去近似 \pi 一样，我们可以按一种方式随机生成大量的树然后去对每种特征去做统计。

具体的思想就是利用极微小的可允许误差去做判断。

举个例子就是比如有两种方法生成一个随机整数，方法 T_1 生成的整数范围为 (-\infty,1]，方法 T_2 生成的整数范围为 [0,\infty)，而且通过随机撒点（随机生成整数）知道：用 T_1 随机生成 2\times 10^5 个整数，其中有 10 个为 1，用 T_2 随机生成 2\times 10^5 个整数，其中有 15 个为 1，那么如果我们得到了一个随机整数 x，若 x\le 0 则判为 T_1 生成，否则为 T_2 生成，出错概率近似可以认为是 P=\dfrac{10}{2\times 10^5}+\dfrac{15}{2\times 10^5}=0.000125。

那么同理，对于判定生成随机树的方式，我们需要寻找一个函数 f(T)，以一棵树 T 为自变量，当 T 用两种不同的随机方法生成时，分别对应的 f(T) 范围是几乎不交的（指按随机撒点的方式出错的样本点个数相对样本总数很小），那么即可在一定可控的误差内做出判定。

用一个 f(T) 作为判断标准判出一种方法，找三个有效的 f(T) 即可。

代码就不给了，给个 maker 吧，这题有趣的地方就在于尝试各种不同的 f(T)。

maker 中附有各个函数的意义及使用方法。（我在跑 maker 的时候都是撒 2\times 10^5 个点）

最终的可行结果是：

• 记 deg 的方差，若方差除以 100000 下取整后 \ge16000 则判定为 1。

• 在之前的基础上，若每个点各个子树大小的对数之和 \ge 11805 则判定为 4。

• 在之前的基础上，若每个点到最远一度点距离之和 \le 2490 则判定为 2，否则为 3。

不保证按本地的随机撒点结果一定可以获得满分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
const int M=1e7+5;
int Head[N],vet[N<<1],Next[N<<1];
int p[N],x[N],y[N],fa[N],f[N],g[N],deg[N],pos[N],vis[N],siz[N],dis[N];
ll vec[M],U[M],D[M];
int L,tp,tq,edgenum,len,res;
int Find(int u){ return fa[u]==u?u:fa[u]=Find(fa[u]); }
void gen1(){  //第一种生成方法
    for (int i=1; i<=1000; i++) p[i]=i;
    random_shuffle(p+1,p+1+1000);
    for (int i=2; i<=1000; i++) x[i-1]=p[rand()%(i-1)+1],y[i-1]=p[i];
}
void gen2(){  //第二种生成方法
    for (int i=1; i<=1000; i++) p[i]=i;
    random_shuffle(p+1,p+1+1000);
    for (int i=2; i<=1000; i++) x[i-1]=p[i/2+rand()%(i-i/2)],y[i-1]=p[i];
}
void gen3(){  //第三种生成方法
    for (int i=1; i<=1000; i++) fa[i]=i;
    int cnt=0;
    while (cnt<999){
        int u=rand()%1000+1,v=rand()%1000+1;
        if (Find(u)!=Find(v)){
            cnt++; x[cnt]=u,y[cnt]=v;
            fa[Find(u)]=Find(v);
        }
    }
}
void gen4(){  //第四种生成方法，随机prufer序列
    for (int i=1; i<=998; i++) p[i]=rand()%1000+1;
    set<int> s;
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=998; i++) vis[p[i]]++;
    for (int i=1; i<=1000; i++)
        if (!vis[i]) s.insert(i);
    for (int i=1; i<=998; i++){
        int t=*s.begin();
        x[i]=t,y[i]=p[i];
        s.erase(t); vis[p[i]]--;
        if (!vis[p[i]]) s.insert(p[i]);
    }
    int t=*s.begin();
    s.erase(t);
    x[999]=t,y[999]=*s.begin();
}
void gen(int t){
    if (t==1) gen1();
    if (t==2) gen2();
    if (t==3) gen3();
    if (t==4) gen4();
}
void dfs(int u, int F){
    f[u]=1,g[u]=0;
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (v==F) continue;
        dfs(v,u);
        if (f[v]+1>f[u]) g[u]=f[u],f[u]=f[v]+1;
        else if (f[v]+1>g[u]) g[u]=f[v]+1;
    }
}
void solve1(){
    int ans=0; dfs(1,0);
    for (int i=1; i<=1000; i++) ans=max(ans,f[i]+g[i]);
    vec[++len]=ans;
}
void solve2(){
    int ans=0;
    for (int i=1; i<=1000; i++) ans+=(deg[i]==2);
    vec[++len]=ans;
}
void solve10(){
    int ans=0; dfs(1,0);
    for (int i=1; i<=1000; i++) ans+=f[i]+g[i];
    vec[++len]=ans;
}
void solve14(){
    int ans=0; dfs(1,0);
    for (int i=1; i<=1000; i++) ans+=f[i]*f[i]+g[i]*g[i];
    vec[++len]=ans/50;
}
void solve3(){
    int ans=0;
    for (int i=1; i<=1000; i++) ans+=deg[i]*deg[i];
    vec[++len]=ans;
}
void solve4(){
    ll ans=0,sum=0;
    for (int i=1; i<=1000; i++) sum+=deg[i];
    for (int i=1; i<=1000; i++) ans+=1ll*(1000*deg[i]-sum)*(1000*deg[i]-sum);
    vec[++len]=ans/100000;
}
void dfs1(int u, int f){
    siz[u]=1; int mx=0;
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        mx=max(mx,siz[v]);
    }
    mx=max(mx,1000-siz[u]);
    if (mx<res) res=mx;
}
int dfs2(int u, int f){
    siz[u]=1; int mx=0,sum=0;
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (v==f) continue;
        sum+=dfs2(v,u);
        siz[u]+=siz[v];
        mx=max(mx,siz[v]);
    }
    mx=max(mx,1000-siz[u]);
    return sum+mx;
}
void solve5(){
    dfs1(1,0); int ans=0;
    for (int i=1; i<=1000; i++) ans+=siz[i];
    vec[++len]=ans;
}
void solve6(){
    dfs1(1,0); int ans=0;
    for (int i=1; i<=1000; i++) ans+=siz[i]*siz[i];
    vec[++len]=ans;
}
void solve7(){
    dfs1(1,0);
    ll ans=0,sum=0;
    for (int i=1; i<=1000; i++) sum+=siz[i];
    for (int i=1; i<=1000; i++) ans+=1ll*(1000*siz[i]-sum)*(1000*siz[i]-sum);
    vec[++len]=ans/100000;
}
void solve8(){ res=1e9; dfs1(1,0); vec[++len]=res; }
void solve9(){ vec[++len]=dfs2(1,0); }
double dfs3(int u, int f){
    siz[u]=1; double sum=0;
    for (int e=Head[u]; e; e=Next[e]){
        int v=vet[e];
        if (v==f) continue;
        sum+=dfs3(v,u);
        siz[u]+=siz[v];
    }
    sum+=log2(siz[u])+log2(1001-siz[u]);
    return sum;
}
void solve11(){ vec[++len]=dfs3(1,0); }
void solve12(){
    queue<int> que; int ans=0;
    for (int i=1; i<=1000; i++)
        if (deg[i]==1) que.push(i),dis[i]=1;
        else dis[i]=1e9;
    while (!que.empty()){
        int u=que.front(); que.pop();
        for (int e=Head[u]; e; e=Next[e]){
            int v=vet[e];
            if (dis[v]!=1e9) continue;
            deg[v]--;
            if (deg[v]==1) que.push(v),dis[v]=dis[u]+1;
        }
        ans+=dis[u]*dis[u];
    }
    vec[++len]=ans;
}
void solve13(){
    int ans=0;
    for (int i=1; i<=1000; i++) ans+=(deg[i]==1);
    for (int i=1; i<=1000; i++) ans-=(deg[i]==2);
    vec[++len]=ans;
}
void solve(int t){
    if (t==1) solve1(); //直径
    if (t==2) solve2(); //二度点个数
    if (t==3) solve3(); //deg的平方和
    if (t==4) solve4(); //deg的方差 
    if (t==5) solve5(); //以1为根的子树大小之和
    if (t==6) solve6(); //以1为根的子树大小的平方和
    if (t==7) solve7(); //以1为根的子树大小的方差
    if (t==8) solve8(); //重心的最大子树大小
    if (t==9) solve9(); //我也不知道这个是在干啥。。。
    if (t==10) solve10(); //每个点子树中最长链+次长链的长度
    if (t==11) solve11(); //每个点各个子树大小的对数之和
    if (t==12) solve12(); //每个点到最远一度点距离的平方和
    if (t==13) solve13(); //一度点个数-二度点个数
    if (t==14) solve14(); //每个点子树中最长链平方+次长链平方
}
inline void addedge(int u, int v){
    edgenum++;
    vet[edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
int main(){
    scanf("%d%d%d",&L,&tp,&tq);
    //L为随机撒点的个数，tp为生成树的方法（标号与题目中相同），tq为尝试的不同函数的编号
    signed a[5000],sum;
    for (int i=0; i<5000; i++) sum+=a[i];
    srand(sum);
    for (int o=1; o<=L; o++){
        gen(tp);
        memset(deg,0,sizeof(deg));
        memset(Head,0,sizeof(Head)); edgenum=0;
        for (int i=1; i<1000; i++){
            addedge(x[i],y[i]),addedge(y[i],x[i]);
            deg[x[i]]++,deg[y[i]]++;
        }
        solve(tq);
        if (o%1000==0) printf("==>%d times\n",o); //表示目前撒了多少样本点了
    }
    ll mn=1e18,mx=-1e18;
    for (int i=1; i<=L; i++) mx=max(mx,vec[i]),mn=min(mn,vec[i]);
    printf("%lld %lld\n",mn,mx);  //特征值的范围

    ll P=0; scanf("%lld",&P); //给出均分[min,max]的长度
    ll cur=mn; int tot=0;
    while (cur<=mx){
        D[++tot]=cur;
        U[tot]=(cur+P-1>=mx?mx:cur+P-1);
        cur+=P;
    }
    for (int i=1; i<=L; i++)
        for (int j=tot; j>=1; j--)
            if (vec[i]<=U[j] && vec[i]>U[j-1]){ pos[j]++; break; }
    for (int i=1; i<=tot; i++) printf("%lld %lld %d\n",D[i],U[i],pos[i]); //表示特征值在[D,U]中的样本点个数
    return 0;
}

好像最终写出来只有 1.4k 比其他代码短得多？