Codeforces Round #523 (Div. 2) F. Katya and Segments Sets (交互题+思维)

时间:2023-10-22 12:28:26

https://codeforces.com/contest/1061/problem/F

题意

假设存在一颗完全k叉树(n<=1e5),允许你进行最多(n*60)次询问,然后输出这棵树的根,每次询问,a,b,c三个点,会返回b是否在a,c之间的路径上

思路

  • 粗略看了下询问次数,可以知道,你最多可以询问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;
}
}
}