正解:构造

解题报告:

传送门!

交互题交互题!哇好新鲜啊QwQ

首先考虑最傻逼的做法,应该是每个人都能想到的

首先看一下它给的条件,考虑到完全二叉树的性质,就可以发现,如果给的邻居只有一个,说明是叶子,有两个,说明是根,有三个,说明是普通的节点

然后就分情况讨论鸭(以下内容都是从最差的情况即h=7为基础的讨论

如果运气好,问到了根,得嘞那就不用再问辣ans出来辣

如果问到了一个叶子节点,那就会给一个非根非叶子节点,就继续询问这个普通节点

如果问到了一个普通节点,就会有三个邻居,那就依次选,并利用已知条件优化一下

具体怎么做我就不说辣反正就是枚举一通+所有人都想得到的优化

说一下正解趴

首先可以想到,假如给一条链,链的一端是叶子节点,那么这条链上每个节点的深度都能知道了是趴

那假如我们第一次问,问到了一个普通节点,现在要求它的深度,怎么求呢

随便问两条链,从三个邻居中选出俩然后一条路问到黑的那种,经过节点数比较少的那条一定是经过它的儿子的笔直向下的一条链(如果相等就都是)(不理解的可以画下图很快就能get辣

同时我们还可以知道三个邻居中哪个是它爹哪些是它崽

然后我们就能get一个构造方法

随机一个点,按照上面的方法求出它的深度

　　　　　　　　↓

找到当前已知深度最低的点

↓　　　　　　　　　　↑

随机一条链,更新当前点祖先的深度,回到操作2

就这么一直做做做下去就能保证一直往上就能找到根节点了嘛

但是继续思考

当h=7的时候,假如运气有这——么背,当询问到深度=2的时候(规定根节点深度为1),如果选一条链通向叶子节点,就要问5次,就会要超过辣

但是考虑,当深度=2的时候,我们未知的邻居节点只有两个,一定有一个是根,所以只要问1次就出来了,问5次肯定亏辣

当深度=3的时候一样,具体不剖析了反正一样是,打破砂锅问到底就很亏不如直接问

最后通过一系列计算可以发现当最惨的情况下也只用问17次,但是第17次问到的一定是树根,所以其实只要问16次,就刚好!

over!

#include<algorithm>

#include<iostream>

#include<cstring>

#include<iomanip>

#include<string>

#include<cmath>

#include<cstdio>

#include<vector>

using namespace std;

#define ll int

#define il inline

#define rg register

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

#define chck(x) if(l[x]==2)return void(print(x));

const ll N=+;

ll h,l[N],a[N][],q[],T,head,tail;

bool used[N],gdgs=;

il void get(ll x){if(used[x])return;cout<<"? "<<x<<endl;cout.flush();used[x]=;cin>>l[x];rp(i,,l[x])cin>>a[x][i];}

il void print(ll x){cout<<"! "<<x<<endl;cout.flush();}

il bool isleaf(ll x){return l[x]==;}

il void solv()

{

    memset(used,,sizeof(used));cin>>h;get();head=tail=;chck();q[]=;

    if(!isleaf())

    {

        q[++tail]=a[][];

        while(gdgs)

        {

            get(q[tail]);if(isleaf(q[tail]))break;

            rp(i,,l[q[tail]])if(a[q[tail]][i]!=q[tail-]){q[tail+]=a[q[tail]][i];++tail;break;}

        }

        q[--head]=a[][];

        while(gdgs)

        {

            get(q[head]);if(isleaf(q[head]))break;

            rp(i,,l[q[head]])if(a[q[head]][i]!=q[head+]){q[head-]=a[q[head]][i];--head;break;}

        }

    }

    ll dep=h-((tail-head)>>),nw=q[(head+tail)>>];

    while(gdgs)

    {

        if(dep<=)

        {

            if(dep==)return void(print(nw));

            rp(i,,l[nw])if(!used[a[nw][i]]){nw=a[nw][i];break;}

            --dep;

            if(dep==)return void(print(nw));

            if(dep==)

            {

                ll tmp[],len=;get(nw);

                rp(i,,l[nw])if(!used[a[nw][i]])tmp[++len]=a[nw][i];

                rp(i,,len-){get(tmp[i]);chck(tmp[i]);}

                return void(print(tmp[len]));

            }

            else

            {

                ll tmp[],len=,tmp2[],len2=;get(nw);

                rp(i,,l[nw])if(!used[a[nw][i]])tmp[++len]=a[nw][i];

                rp(i,,len){get(tmp[i]);rp(j,,l[tmp[i]])if(!used[a[tmp[i]][j]])tmp2[++len2]=a[tmp[i]][j];}

                rp(i,,len2-){get(tmp2[i]);chck(tmp2[i]);}

                return void(print(tmp2[len2]));

            }

        }

        head=tail=;q[tail]=nw;

        while(gdgs)

        {

            get(q[tail]);if(isleaf(q[tail]) && tail>)break;chck(q[tail]);

            rp(i,,l[q[tail]])if(!used[a[q[tail]][i]]){q[tail+]=a[q[tail]][i];++tail;break;}

        }

        nw=q[(tail-h+dep)>>];dep-=(tail-h+dep)>>;

    }

}

int main()

{

    cin>>T;

    while(T--)solv();

}

代码有这——么难打呜呜呜!

巴特西

CF750F New Year and Finding Roots 构造+树论

正解:构造

解题报告:

最新文章

热门文章