CF2133C The Nether 题解

· · 题解

交互题，如果把 n\le 500 的限制改成 n\le 5000 是不是会更好一点？

我们记 l_i 表示以 i 开头的最长链。

首先我们能用 n 次交得到 l_i，并且找到其中一个最长链的第一个元素 x，发现最大的 l_i 必然是一个最长链的首端。

证明：如果 i 不是这个最长链的第一个元素，那么假设 j 连向 i，则 l_j=l_i+1，那么 l_i 就不是最大值，矛盾。

然后我们就选择一个链，先找到它的首端。

接下来的问题是：我们如何找到一个点 v，满足点 u 直接连向点 v？

这个应该是好交互的。我们枚举 v，然后直接交互即可，具体操作见代码。

时间复杂度 O(n^2)。后面找点是有 O(n\log n) 的实现的，读者可以尝试着去对我的代码进行优化。瓶颈在于输出。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int n;
int a[N];
int id[N];
bool cmp(int x,int y){
    return a[x]>a[y];
}
void solve(){
    cin>>n;
    int l=0;
    for(int i=1;i<=n;i++){
        // ? i n 1 2 3 ... n 即以 i 为开头，可以在全图跑的最长链
        cout<<"? ";
        cout<<i<<" "<<n<<" ";
        for(int j=1;j<=n;j++)cout<<j<<" ";//真正的瓶颈在于这里 :(
        cout<<"\n";
        fflush(stdout);
        cin>>a[i];
        l=max(l,a[i]);
        id[i]=i;
    }
    sort(id+1,id+n+1,cmp);//提示
    vector<int>ans;
    int idd=1;
    for(int i=1;i<=n;i=idd){
        ans.push_back(id[i]);
        if(a[id[i]]==1)break;
        for(int j=1;j<=n;j++){//这里完全可以优化至 O(n\log n)，感兴趣的读者可以思考一下，有前后两个提示
            if(a[id[i]]-a[id[j]]==1){//提示
                //id[i] 2 id[i] id[j]，即以 id[i] 为开头，可以跑 id[i] 和 id[j] 的最长路 这是可以判定 id[i] 是否连向 id[j] 的
                cout<<"? "<<id[i]<<" 2 "<<id[i]<<" "<<id[j]<<"\n";
                fflush(stdout);
                int x;
                cin>>x;
                if(x==2){
                    idd=j;
                    break;
                }
            }
        }
    }
    cout<<"! "<<ans.size()<<" ";
    for(auto x:ans)cout<<x<<" ";
    cout<<"\n";
    fflush(stdout);
    return;
}
signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}
/*

*/