[CF1061F] Lost Root

题目链接

Solution

唔……随机化……

随机两个点 $u,v$，然后枚举所有点询问是否在 $u,v$ 路径上，记录在路径上的点的个数，如果个数等于 $2h-1$，那么 $u,v$ 就是两个叶节点且根在其路径中间，一直循环随机直到找到这样的点（每次循环找到的概率是 $\frac{1}{8}$）。

开一个链表，依次把 $u,v$ 路径上的点拿出来与链表中的点询问，判断它在链表中的位置，插入链表；该过程结束后根节点就是链表中间的那个节点。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int n, k;
map<tuple<int, int, int>, bool> store;
map<pair<int, int>, bool> asked;

inline bool ask(int x, int y, int z){
    if(store[make_tuple(x, y, z)])
        return store[make_tuple(x, y, z)];
    printf("? %d %d %d\n", x, y, z);
    fflush(stdout);
    char s[10];
    scanf("%s", s);
    store[make_tuple(x, y, z)] = s[0] == 'Y';
    return s[0] == 'Y';
}

int main(){
    srand(19950523);
    read(n, k);
    int h, tot;
    for(h = 0, tot = 1; tot < n * (k - 1) + 1; h++, tot *= k);
    while(1){
        int u = rand() % n + 1, v = rand() % n + 1;
        while(v == u)   v = rand() % n + 1;
        if(asked[make_pair(u, v)] || asked[make_pair(v, u)])    continue;
        asked[make_pair(u, v)] = asked[make_pair(v, u)] = true;
        vector<int> vec;
        int cnt = 2;
        for(int i = 1; i <= n; i++){
            if(i == u || i == v)    continue;
            if(ask(u, i, v)){
                cnt++;
                vec.emplace_back(i);
            }
        }
        if(cnt != 2 * h - 1)    continue;
        list<int> node;
        node.emplace_front(v);
        random_shuffle(vec.begin(), vec.end());
        for(auto k: vec){
            for(list<int>::iterator it = node.begin(); it != node.end(); it++){
                if(ask(u, k, (*it))){
                    node.emplace(it, k);
                    break;
                }
            }
        }
        cnt = 0;
        list<int>::iterator it;
        for(it = node.begin(); it != node.end(); it++){
            cnt++;
            if(cnt == h - 1)    break;
        }
        printf("! %d\n", (*it));
        fflush(stdout);
        return 0;
    }
}