正題

luogu
CF1061F

---

題目大意

給出n和k，現(xiàn)在有一顆n個(gè)點(diǎn)的滿k叉樹，每次查詢可以問一個(gè)點(diǎn)是否在另外兩個(gè)點(diǎn)的路徑上，讓你在 $60\times n$ 次詢問內(nèi)得到根節(jié)點(diǎn)

---

解題思路

因?yàn)槭菨Mk叉數(shù)，可以先得到深度dep

每次隨機(jī)找兩個(gè)點(diǎn)，用 n 次查詢判斷這兩個(gè)點(diǎn)路徑之間的點(diǎn)數(shù)，如果為 $dep\times 2?1$ 就是根節(jié)點(diǎn)兩個(gè)不同子樹中的葉子結(jié)點(diǎn)，那么根節(jié)點(diǎn)一定在該路徑上，然后暴力判斷那個(gè)點(diǎn)是根節(jié)點(diǎn)即可（到葉子結(jié)點(diǎn)路徑長度為dep）

因?yàn)槿~子結(jié)點(diǎn)的數(shù)量大于 $\frac{n}{2}$，所以隨機(jī)到兩個(gè)葉子結(jié)點(diǎn)的概率是 $\frac{1}{4}$，隨機(jī)到不同子樹的概率為 $\frac{k?1}{k}$，所以找到符合條件的兩個(gè)葉子結(jié)點(diǎn)的概率為 $\frac{k?1}{4k}$，當(dāng)k=2時(shí)，概率最小，為$\frac{1}{8}$

期望可以在規(guī)定次數(shù)內(nèi)找到答案

---

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)//暴力判斷那個(gè)點(diǎn)是根節(jié)點(diǎn)if(p[i][1]&&get(x,i,0)==dep){printf("! %d\n",i);return 0;}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【交互】【随机】Lost Root（CF1061F）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。