D. Tournament Countdown

48 阅读 0 评论 32 点赞

我是靠谱客的博主勤奋犀牛，最近开发中收集的这篇文章主要介绍D. Tournament Countdown，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接
在这里插入图片描述

题意：
1：交互题
2：给出n
3：共有2 ^ n个队员
4：？ a b 的意思是向系统询问a，b谁赢的场数多（即谁处于图中的更高层）
5：最终结果表示为 ! res
6：最多询问次数是 (2/3)*(2^(n+1) ) 上取整
题解：我们可以计算一下，如果我们两两询问，最终的询问次数是2^(n+1)-1是高于题目限制次数，那么我们就开始想这减少询问次数。

我们尝试着四个一询问，我们以 1，2，3，4为例：两个一组，假设我们比较1，3，当两个相等的时候，他们一定是在最低层；但是如果1>3的话，可能1，3都在第二层，这种情况下如果我们仍然期望确定第二层的数量是不行的，这样询问次数在最坏的情况下仍然是2^(n+1)的，所以我们这里直接确定第三层（即向上两层），这种情况下，我们最多询问两次就可以确定上两层的数。我们可以计算一下询问数量，本来三次才能确定两层的数字，现在只需要询问两次，这样就是(2/3 * 2 ^ (n+1))正好符合题中的限制次数。

下面是AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> vec;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,num=1;
        cin>>n;
        vec.clear();
        for(int i=1;i<=n;i++) num*=2;
        for(int i=1;i<=num;i++) vec.push_back(i);
        if(num>=4)
        {
            while(vec.size()>2)
            {
                int len=vec.size();
                for(int i=0;i<len;i+=4)
                {
                    cout<<"?"<<" "<<vec[i]<<" "<<vec[i+2]<<endl;
                    //cout.flush();
                    int x;
                    cin>>x;
                    if(x==1)
                    {
                        cout<<"?"<<" "<<vec[i]<<" "<<vec[i+3]<<endl;
                        //cout.flush();
                        int x;
                        cin>>x;
                        if(x==1) vec.push_back(vec[i]);
                        else if(x==2) vec.push_back(vec[i+3]);
                    }
                    else if(x==2)
                    {
                        cout<<"?"<<" "<<vec[i+1]<<" "<<vec[i+2]<<endl;
                        //cout.flush();
                        int x;
                        cin>>x;
                        if(x==1) vec.push_back(vec[i+1]);
                        else if(x==2) vec.push_back(vec[i+2]);
                    }
                    else if(x==0)
                    {
                        cout<<"?"<<" "<<vec[i+1]<<" "<<vec[i+3]<<endl;
                        //cout.flush();
                        int x;
                        cin>>x;
                        if(x==1) vec.push_back(vec[i+1]);
                        else if(x==2) vec.push_back(vec[i+3]);
                    }
                }
                vec.erase(vec.begin(),vec.begin()+len);
            }
        }
        cout<<"?"<<" "<<vec[0]<<" "<<vec[1]<<endl;
        //cout.flush();
        int x;
        cin>>x;
        if(x==1) cout<<"!"<<" "<<vec[0]<<endl;
        else cout<<"!"<<" "<<vec[1]<<endl;
    }
    return 0;
}