Codeforces Round 865 (Div. 2) D题

倪丹

D. Sum Graph
题意：

      首先这是一道交互题目，在题目中会给出一个长度为n的隐藏排列，你需要通过两种操作来推测出这个隐藏排列（注意你可以输出两个排列，只要排列之一为正确，答案便可以通过。）
     操作1：输出一个x ，满足2<=x<=2*n，然后对于每一个i，满足1<=i<=n且1<=x-i<=n，此时点i和x-i将会相连。
     操作2：输出两个值x和y，表明数组中的第x个数和第y个数，告知你他们之间的最短路径为多长，若没有最短路径便输出－1；
     你的操作数量被限制在2*n次。
分析：

      我们可以有两种想法：
      1.第一种是一边连接，一边询问距离。显然这样的做法，每次我们新加入的边难以控制，每次询问之后得到的距离也有很多情况对应，这种方法不太现实。
      2.第二种就是正确的想法，我们尝试把每个点连接起来，并且使他们的距离都不一样，这样我们每次询问就可以得到一个点的正确值。不难注意到，选择x=n+1，以及x=n+2，这样的选择会形成1－n－2－(n-1)－3－(n-2)后面依次类推的链。那么事情就非常简单了，首先我们随便询问一个点和其他点的所有距离并且记录距离，有最长边的点就一定是上述链的两个端点，因为可以输出两个排列，这样我们就相当于知道了这点它原本的值。（因为他有两种情况，而这两种情况我们都可以输出）然后我们再询问这个点和其他点的距离，由于每个点与此点的距离不同，所以每询问一次都可以得到一个答案。总询问在2*n内。
代码部分：

#include<bits/stdc++.h>
using namespace std;

int ask(int x,int y){
    cout<<'?'<<' '<<x<<' '<<y<<endl;
    int l;
    cin>>l;
    return l;
}

struct bi{
     int len;
     int id;
};

bool cmp(bi x,bi y){
     return  x.len>y.len;
}

int main(){
    int t;
    cin>>t;
    while(t--){
       int n;
       cin>>n;
       int w;
       cout<<'+'<<' '<<n+1<<endl;
       cin>>w;
       cout<<'+'<<' '<<n+2<<endl;
       cin>>w;
       vector<bi>arr(n);
       arr[0].len=0;
       arr[0].id=1;
       for(int i=1;i<=n-1;i++){
           arr.len=ask(1,i+1);
           arr.id=i+1;
       }
       sort(arr.begin(),arr.end(),cmp);
       int l=1,r=n;
       int brr[n];//这里是算出我们推导的链
       for(int i=0;i<=n-1;i++){
           if(i&1){
            brr=r;
            r--;
            }
            else {
              brr=l;
              l++;
            }
       }
       int crr[n];
       int drr[n];
       crr[arr[0].id-1]=brr[0];
       drr[arr[0].id-1]=brr[n-1];
       crr[0]=brr[arr[0].len];
       drr[0]=brr[n-1-arr[0].len];
       for(int i=1;i<=n-1;i++){
           if(arr[0].id==i+1)continue;
           int q=ask(arr[0].id,i+1);
           crr=brr[q];
           drr=brr[n-1-q];
       }
       cout<<'!'<<' ';
       for(int i=0;i<=n-1;i++){
          cout<<crr<<' ';
        }
        for(int i=0;i<=n-1;i++){
          cout<<drr<<' ';
        }
        cout<<endl;
        int kw;
        cin>>kw;
        if(kw==-2){
           return 0;
        }
     }     
    return 0;
}

注：如果思路没错，大概是题目的要求没写仔细，别问我为什么知道，因为我昨晚就是因为没看到各种返回值，一晚上都没过。

风水及命理大师

请问crr[0]=brr[arr[0].len]是怎么提前求出来的[捂脸]
按正常思路不是全部让下面那个循环去询问吗

这生活会不会有点难

首先因为我们一开始找的点不一定是端点，所以我们先通过一个点和其他所有点的询问，选择出与他距离最远的点，这个点一定是两个端点，因为所有点都在链上。全通过下面循环得到每个点的结果，它的前提是要每一个点的距离都不一样，换一句话来说就是每次询问的时候，得到的距离都不一样，而在我们已经构造好的链上，只有以两个端点对于其他点的询问，才会使距离都不一样。

快递小哥

然后就是你说的这一步，因为一开始我们通过一个点去和其他点询问（我默认的是第一个点），crr[0]=brr[arr[0].len]，这两个点之间也就是第一个点和第arr[0].id+1个点，它们之间的距离在第一轮询问中其实就已经知道了。所以可以直接写出来。当然您觉得放到下面的循环写其实也是没问题的。首先两次添加操作，第一轮循环访问n-1次询问操作，第二轮循环n-1次询问操作，这部放到下面循环写也是对的。

夏时蝉

我重新想了下，因为一开始设的就是从排列的第一个来求，所以距离和位置提前已经确定了，刚刚猪B了[捂脸]