肯德基的网站建设,重庆网络技术有限公司,重庆 网站建设,免费dns二级域名正题
luogu CF1061F 题目大意
给出n和k#xff0c;现在有一颗n个点的满k叉树#xff0c;每次查询可以问一个点是否在另外两个点的路径上#xff0c;让你在 60n60\times n60n 次询问内得到根节点 解题思路
因为是满k叉数#xff0c;可以先得到深度dep
每次随机找两个点现在有一颗n个点的满k叉树每次查询可以问一个点是否在另外两个点的路径上让你在 60×n60\times n60×n 次询问内得到根节点 解题思路
因为是满k叉数可以先得到深度dep
每次随机找两个点用 n 次查询判断这两个点路径之间的点数如果为 dep×2−1dep\times 2-1dep×2−1 就是根节点两个不同子树中的叶子结点那么根节点一定在该路径上然后暴力判断那个点是根节点即可到叶子结点路径长度为dep
因为叶子结点的数量大于 n2\frac{n}{2}2n所以随机到两个叶子结点的概率是 14\frac{1}{4}41随机到不同子树的概率为 k−1k\frac{k-1}{k}kk−1所以找到符合条件的两个叶子结点的概率为 k−14k\frac{k-1}{4k}4kk−1当k2时概率最小为18\frac{1}{8}81
期望可以在规定次数内找到答案 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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 sum2;p[x][g]p[y][g]0;for(int i1;in;i){if(ix||iy)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);xn;y1;while(x){x-y;y*k;dep;}while(1){xrand()%n1;yrand()%n1;while(xy||d[x][y]){xrand()%n1;yrand()%n1;}d[x][y]1;d[y][x]1;if(get(x,y,1)dep*2-1){//找到了for(int i1;in;i)//暴力判断那个点是根节点if(p[i][1]get(x,i,0)dep){printf(! %d\n,i);return 0;}}}return 0;
}
