题解我就是不交到洛谷上！
交互题普遍难度虚高。
这种大便交互题一般有个特别逆天的常数，在这道题上是 $420$。
你考虑那个大常数咋用。
我们发现每次询问的本质是树上到 $u,v,w$ 距离的和最小的节点。
你考虑一个节点被作为答案回答的次数，发现如果这个点的三棵子树的大小为 $a,b,c$ （不足三棵子树的用 $0$ 补全），那么答案就是：$a\times b\times c$。
然后你发现一个很显然的事实，就是你发现出现次数最多的点，是根节点的两棵子树的根。
如果我们得到了那两个根（设为 $r_1,r_2$），那么就可以直接询问 $n-2$ 遍 $(r_1,r_2,i)$，当回答的是 $i$ 的时候，那个 $i$ 就是根，直接输出就行了，证明是显然的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<bits/stdc++.h>
using namespace std;
mt19937 rd((unsigned long long)new char);
int n,h,cnt[1000005],cnt2[1000005];
int main(){
cin>>h;n=(1<<h)-1;
for(int i=1;i<=420;++i){
int x=rd()%n+1,y=rd()%n+1;
while(y==x)y=rd()%n+1;
int z=rd()%n+1;
while(z==x||z==y)z=rd()%n+1;
cout<<"? "<<x<<' '<<y<<' '<<z<<endl;
int t;cin>>t;++cnt[t];
}
int mx1=-1,mx2=-2,id1=0,id2=0;
for(int i=1;i<=n;++i){
if(cnt[i]>mx1)mx2=mx1,mx1=cnt[i],id2=id1,id1=i;
else if(cnt[i]>mx2)mx2=cnt[i],id2=i;
}
for(int i=1;i<=n;++i){
if(id1==i||id2==i)continue;
cout<<"? "<<id1<<' '<<id2<<' '<<i<<endl;
int x;cin>>x;
if(x==i){cout<<"! "<<x<<endl;return 0;}
}
return 0;
}
|
