【交互】【随机】Lost Root（CF1061F）

2024-01-29 23:18

文章标签 交互随机 lost cf1061f

本文主要是介绍【交互】【随机】Lost Root（CF1061F），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

luogu
CF1061F

题目大意

给出n和k，现在有一颗n个点的满k叉树，每次查询可以问一个点是否在另外两个点的路径上，让你在 $60\times n$ 次询问内得到根节点

解题思路

因为是满k叉数，可以先得到深度dep

每次随机找两个点，用 n 次查询判断这两个点路径之间的点数，如果为 $dep\times 2-1$ 就是根节点两个不同子树中的叶子结点，那么根节点一定在该路径上，然后暴力判断那个点是根节点即可（到叶子结点路径长度为dep）

因为叶子结点的数量大于 $\frac{n}{2}$ ，所以随机到两个叶子结点的概率是 $\frac{1}{4}$ ，随机到不同子树的概率为 $\frac{k-1}{k}$ ，所以找到符合条件的两个叶子结点的概率为 $\frac{k-1}{4k}$ ，当k=2时，概率最小，为 $\frac{1}{8}$

期望可以在规定次数内找到答案

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1510
using namespace std;
int n,k,x,y,dep,p[N][2],d[N][N];
char s[10];
int get(int x,int y,int g)//判断路径长度
{int sum=2;p[x][g]=p[y][g]=0;for(int i=1;i<=n;++i){if(i==x||i==y)continue;printf("? %d %d %d\n",x,i,y);fflush(stdout);scanf("%s",s);if(s[0]=='Y')sum++,p[i][g]=1;else p[i][g]=0;}return sum;
}
int main()
{srand(2018729);scanf("%d%d",&n,&k);x=n;y=1;while(x){x-=y;y*=k;dep++;}while(1){x=rand()%n+1;y=rand()%n+1;while(x==y||d[x][y]){x=rand()%n+1;y=rand()%n+1;}d[x][y]=1;d[y][x]=1;if(get(x,y,1)==dep*2-1){//找到了for(int i=1;i<=n;++i)//暴力判断那个点是根节点if(p[i][1]&&get(x,i,0)==dep){printf("! %d\n",i);return 0;}}}return 0;
}