Forethought Future Cup - Elimination Round C 二分 + 交互(求树的直径)

https://codeforces.com/contest/1146/problem/C

题意

一颗大小为n的树,每次可以询问两个集合,返回两个集合中的点的最大距离,9次询问之内得出树的直径

题解

求树的直径:先找到一个点a,找到离他最远的一个点b,最后找到距离b最远的点c,b和c之间的距离就是树的直径
先询问离1最远的距离,然后二分找到这个点a,然后询问a的最远距离

代码

#include<bits/stdc++.h>

#define fk fflush(stdout)

using namespace std;

int T,x;

int qy(int l,int r){

    printf("1 %d 1",r-l+1);

    for(int i=l;i<=r;i++)printf(" %d",i);

    printf("\n");

    fk;

    int x;

    scanf("%d",&x);

    return x;

}

int main(){

    scanf("%d",&T);

    while(T--){

        int ans,n;

        scanf("%d",&n);

        printf("1 %d",n-1);

        for(int i=1;i<=n;i++)printf(" %d",i);

        printf("\n");

        fk;

        scanf("%d",&x);

        int l=2,r=n,mid;

        while(l<r){

            mid=(l+r)/2;

            if(qy(l,mid)<x)l=mid+1;

            else r=mid;

        }

        printf("1 %d",n-1);

        printf(" %d",l);

        for(int i=1;i<=n;i++)if(l!=i)printf(" %d",i);

        printf("\n");

        fk;

        scanf("%d",&ans);

        printf("-1 %d\n",ans);

        fk;

    }

}

巴特西

Forethought Future Cup - Elimination Round C 二分 + 交互(求树的直径)

题意

题解

代码

最新文章

热门文章