自动搬运

查看原文

来自洛谷，原作者为

	wishapig 最黑的那段路，终究是要自己走完的

搬运于2025-08-24 22:14:45，当前版本为作者最后更新于2021-12-23 11:26:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：

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

$1\le m\le 4000$

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

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

就像在正方形里随机撒点去近似 $\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 比其他代码短得多？