https://codeforces.com/contest/1061/problem/F
题意
思路
- 粗略看了下询问次数，可以知道，你最多可以询问60对不同的点，每对点遍历n个点，可以知道n个点在不在这两个点的中间
- 一开始的思路是，随机找两个点，遍历所有点，然后记录在他们中间的点，在里面再找两个点，继续上述操作，知道剩下一个点，但是假设某一步挑出的两个点的路径不经过根节点，hack
- 假设树根在第0层，根据完全k叉树的性质，前k-1层点数为\(2^k-1\),第k层点数为\(2^k\),所以大约就是1:1,那么每次问出一个点是否为叶子的概率是1/2,所以可以先找出两个叶子，然后再询问出两个叶子的路径，中间的点就是根节点
- 叶子结点怎么找：将叶子节点作为中间的点，随便找一个另外一个节点，那么叶子结点不在这个节点和其他节点的路径上，询问次数n
规律
- 完全k叉树，叶子：非叶子 约等于 1:1
- 生成随机数后加一个质数再取模，会使数据更加离散，
- 树的叶子十分重要
- 交互题一定要优化到最简询问次数，不然很容易被hack
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
char s[10];
int n,k,d,a,b,vi[2000],i,cnt;
vector<int>p,P;
int pw(int bs,int x){
int ans=1;
while(x){
if(x&1)ans*=bs;bs*=bs;x>>=1;
}
return ans;
}
void op(int a,int b,int x){
vector<int>tp;
memset(vi,0,sizeof(vi));
int cnt=0;
for(int i=1;i<=n;i++){
if(a==i||b==i)continue;
printf("? %d %d %d\n",a,i,b);
fflush(stdout);
scanf("%s",s);
if(s[0]=='Y'){vi[i]=1;cnt++;}
if(x==0&&cnt==2*d-3)break;
if(x&&cnt>d-2)break;
}
for(int i=1;i<=n;i++)if(vi[i])tp.pb(i);
if(x==0)P=tp;
else p=tp;
}
int main(){
scanf("%d %d",&n,&k);
for(d=1;;d++)if((pw(k,d)-1)/(k-1)==n)break;
for(;;){
a=(rand()+4399)%n+1;b=(rand()+2755)%n+1;
if(a==b){b++;b=b%n+1;}
op(a,b,0);
if(P.size()==2*d-3)break;
}
for(i=0;i<P.size();i++){
op(P[i],a,1);
if(p.size()==d-2){
printf("! %d\n",P[i]);
fflush(stdout);
return 0;
}
}
}