CF1061F Lost Root 题解 / 随机化 交互

题面传送门：CF1061F Lost Root。

首先对于一个路径 \(a,b\)，我们可以 \(n\) 次询问得到长度，我发现对于一个深度为 \(dep\) 的 \(k\) 叉树来说，直径长度为 \(2dep-1\)，因此我们可以随机路径来找到直径。

考虑计算一下二叉树随路径为直径的概率 \(\frac{2^{dep-2} \times 2^{dep-2}}{(2^{dep}-1)^2}\approx \frac{1}{16}\)，随机个 \(30\) 次基本上就能找到了，而对于 \(k>2\) 叉树随到直径的概率显然更高。

由于根一定在直径上且直径的长度为 \(\log\) 量级，我们可以暴力枚举直径上的点，然后判断离叶子的距离是否为 \(dep\) 即可。

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
inline int read(){
	char c=getchar();
	int f=1,ans=0;
	while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
	while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
	return ans*f;
}
mt19937_64 randd(time(0));
inline int ask(int a,int b,int c){printf("? %lld %lld %lld\n",a,b,c);fflush(stdout);string s;cin>>s;return s=="Yes"?1:0;} 
const int N=2010;
int vis[N];
main(){
	int n=read(),k=read();
	int dep=0,tmp=n*(k-1)+1;
	while(tmp!=1) dep++,tmp/=k;
	while(1){
		int a=randd()%n+1,b=randd()%n+1,sum=0;
		for (int i=1;i<=n;i++) sum+=(vis[i]=ask(a,i,b));
		if (sum==2*dep-1){
			for (int i=1;i<=n;i++) if (vis[i]){
				int cnt=0;
				for (int j=1;j<=n;j++) cnt+=ask(a,j,i);
				if (cnt==dep){printf("! %lld\n",i);fflush(stdout);return 0;}
			}
		}
	}
    return 0;
}