Olha and Igor

题目描述

点此看题

解法

自己想了一个 \(O(n^2)\) 的做法，好像也要基于 \(\tt lca\) 的出现频率这东西（多少沾点边了）

考虑询问 \((u,v,w)\) 的另一种意义：在树上找到点 \(x\)，使得 \(d(u,x)+d(v,x)+d(w,x)\) 最小。

发现如果我们随机三个不同的点问一次 \((u,v,w)\)，考虑分析得到的结果：

• 不可能是叶子。
• 如果返回的 \(x\) 是真正的根，必须要其中一个点恰好是根，另外两个点分居左右子树。
• 如果其中两个点在左子树，另外一个点在右子树，一定直接得到根的左儿子。
• 如果其中两个点在右子树，另外一个点在左子树，一定直接得到根的右儿子。
• 根据数感，出现其他的概率远小于根的左右儿子情况（概率可以计算出来，但是我懒）

那么我们可以随机 \(420\) 次，认为出现频率最大的两个点就是根的左右儿子。设得到了 \(x,y\)，那么我们枚举根，如果询问 \((x,y,i)\) 得到 \(i\)，那么 \(i\) 就是真正的根，发现最坏情况下询问次数 \(n+420\)

#include <cstdio>
#include <random>
#include <algorithm>
using namespace std;
const int M = 1000005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,h,a[M],p[M];
int ask(int u,int v,int w)
{
	printf("? %d %d %d\n",u,v,w);
	fflush(stdout);
	return read();
}
signed main()
{
	h=read();n=(1<<h)-1;
	mt19937 z(114514);
	for(int i=0;i<420;i++)
	{
		int u=z()%n+1,v=z()%n+1,w=z()%n+1;
		while(u==v) v=z()%n+1;
		while(u==w || v==w) w=z()%n+1;
		a[ask(u,v,w)]++;
	}
	for(int i=1;i<=n;i++) p[i]=i;
	sort(p+1,p+1+n,[&](int i,int j)
	{return a[i]>a[j];});
	int x=p[1],y=p[2];
	for(int i=1;i<=n;i++)
		if(i!=x && i!=y && ask(x,y,i)==i)
		{
			printf("! %d\n",i);
			fflush(stdout);
			return 0;
		}
}