D. Tournament Countdown

题目链接

题意：
1：交互题
2：给出n
3：共有2 ^ n个队员
4：？ a b means to ask the systema,bWhoever wins the most games（i.e. who is at a higher level in the graph）
5：The final result is expressed as ! res
6：The maximum number of inquiries is (2/3)*(2^(n+1) ) 上取整
题解：我们可以计算一下,If we ask two by two,The final number of inquiries is2^(n+1)-1is higher than the limit of the number of questions,Then we started thinking about reducing the number of inquiries.

We tried four one inquiries,我们以 1,2,3,4为例：两个一组,Suppose we compare1,3,when the two are equal,They must be at the lowest level;但是如果1>3的话,可能1,3all on the second floor,In this case it is not feasible if we still expect to determine the number of second layers,This way the number of inquiries is still in the worst case2^(n+1)的,So we directly determine the third layer here（That is, two floors up）,这种情况下,We can determine the number of the upper two floors by asking twice at most.We can count the number of queries,Originally, it took three times to determine the numbers for the two floors,Now just ask twice,这样就是(2/3 * 2 ^ (n+1))Exactly meet the limit in the question.

下面是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;
}

This question requires addingcout.flush()的,But not right.