题解：P12428 [BalticOI 2025] Tower

_Ch1F4N_ · 2025-06-03 20:11:13 · 题解

很抽象的题目。

首先看到评分标准是所有测试用例的平均次数而不是最大次数与数据随机生成，考虑随机化做法。

对于一个初始的长度为 n 的圆上的 x,y，假若我们把其他点全部问一遍，那么就可以把点分为三类，距离 x 较为近的，距离 y 较近的，和距离 x,y 都比较远的。

三类点都构成圆的一段弧，但是第三类点可能构成优弧，这是我们不希望看到的，因为处理优弧上问题时可能出现两个优弧上的点最短路径不在优弧上的情况，考虑合理的选择 x,y 以规避第三类点出现。

不难发现不出现第三类点（或者第三类点只包含一个单独的点）的充要条件是 dis(x,y) \geq \frac{n}{3}，也就是我们希望尽可能选较长的弧。

考虑这样一个算法：先随机选取一对 x,y，然后依次考虑剩下的点，如果剩下的点 u 与 x,y 询问一次后 x,y 是唯一的最短边，那么就让 y \gets u，看上去这个东西很对，写个暴力发现，对于 n=500 的情况，这个东西跑一轮大概只有 \frac{3}{1000} 的概率跑不出符合条件的 x,y，而这个题只需要保证平均次数限制，所以这个算法是可以接受的。

实际上问出一组满足条件的 x,y 后，圆会被对等分开（也可能存在 0 \sim 2 个分界点），显然切割出来的都是劣弧，其上两点的最短路径一定全部在劣弧上，故可以使用类似上面的算法继续分治下去，合并弧首先考虑如果询问问出来了分界点，直接把分界点分别拼接在两条弧两侧即可，否则考虑合并两条有序的弧 L_1,L_2 时，先令 |L_1| \leq |L_2|，然后取出 L_1 的两个端点与 L_2 的一个端点，如果是 L_2 被取出的端点与 L_1 相邻，那么问出来一定满足 L_1 的两个端点之间的边不是最短边，否则一定满足 L_1 的两个端点之间的边是最短边（注意到保证了 |L_1| \leq |L_2|），然后再考虑更换 L_2 选取的端点或者究竟是与 L_1 哪个端点相邻即可。

询问次数大概是 O(n \log n) 的，实际表现压根不会算，我感觉怎么都不可能常数小于 1 于是就打开了题解看是不是有高明做法，但是发现题解也是类似的随机化，然后我实现了上文的算法，加上对询问记忆化以及特判处理的弧弧长等于 3 的情况（此时只用问一次，弧长更小显然压根不用问）就直接通过了，非常震撼。

由于某些原因写代码的过程比较曲折，所以代码未必能看。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 600;
mt19937 rd(114514);
int n;
vector<int> X,Y;
int r;
map< pair<int,int>,vector< pair<int,int> > > dp[maxn];
void ask(int a,int b,int c){
    vector<int> so;
    so.resize(3);
    so[0]=a,so[1]=b,so[2]=c;
    sort(so.begin(),so.end());
    a=so[0],b=so[1],c=so[2];
    if(dp[a].find(make_pair(b,c))!=dp[a].end()){
        r=0;
        X.clear();
        Y.clear();
        vector< pair<int,int> > res=dp[a][make_pair(b,c)];
        r=res.size();
        X.resize(r),Y.resize(r);
        for(int i=0;i<r;i++){
            X[i]=res[i].first,Y[i]=res[i].second;
        }
        return ;
    }
    cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
    r=0;
    X.clear();
    Y.clear();  
    cin>>r;
    X.resize(r),Y.resize(r);
    vector< pair<int,int> > res;
    for(int i=0;i<r;i++){
        cin>>X[i]>>Y[i];
        res.push_back(make_pair(X[i],Y[i]));
    }
    dp[a][make_pair(b,c)]=res;
}
bool check(int a,int b,int c,int d){
    return max(a,b)==max(c,d)&&min(a,b)==min(c,d); 
}
bool chk(int a,int b,int c){
    ask(a,b,c);
    vector< pair<int,int> > ans;
    ans.resize(r);
    while(r--) ans[r].first=X[r],ans[r].second=Y[r];
    for(pair<int,int> now:ans){
        if(check(now.first,now.second,a,b)==true) return true;
    }
    return false;
}
int cnt=0;
vector<int> solve(vector<int> vec){
    if(vec.size()==3){
        ask(vec[0],vec[1],vec[2]);
        vector<int> res;
        if(Y[0]!=X[1]&&Y[0]!=Y[1]) swap(X[0],Y[0]);
        res.push_back(X[0]);
        res.push_back(Y[0]);
        if(X[1]!=Y[0]) swap(X[1],Y[1]);
        res.push_back(Y[1]);
        return res;
    }
    if(vec.size()<=2) return vec;
    shuffle(vec.begin(),vec.end(),rd);
    int u=vec[0],v=vec[1];
    vector<int> L1,L2;
    L1.push_back(u);
    L2.push_back(v);
    int cut=-1;
    vector<int> res;
    for(int i:vec){
        if(i!=u&&i!=v){
            ask(u,v,i);
            vector< pair<int,int> > ans;
            ans.resize(r);
            while(r--) ans[r].first=X[r],ans[r].second=Y[r];
            for(pair<int,int> now:ans){
                if(check(now.first,now.second,u,v)==true) return res;
            }
            assert(ans.size()<=2);
            if(ans.size()==2) cut=i;
            else{
                if(check(ans[0].first,ans[0].second,u,i)==true) L1.push_back(i);
                else L2.push_back(i);
            }
        }
    }
    vector<int> Vec=vec,l1=L1,l2=L2;
    sort(Vec.begin(),Vec.end());
    sort(l1.begin(),l1.end());
    sort(l2.begin(),l2.end());
    while(1){
        vector<int> res=solve(L1);
        if(res.size()==L1.size()){
            L1=res;
            break;
        }
    }
    while(1){
        vector<int> res=solve(L2);
        if(res.size()==L2.size()){
            L2=res;
            break;
        }
    }
    for(int x:L1){
        if(x==cut) assert(0);
    }
    for(int x:L2){
        if(x==cut) assert(0);
    }
    if(cut==-1){
        if(L2.size()<L1.size()) swap(L1,L2);
        ask(L1[0],L1.back(),L2[0]);
        vector< pair<int,int> > ans;
        ans.resize(r);
        while(r--) ans[r].first=X[r],ans[r].second=Y[r];
        bool flag=false;
        for(pair<int,int> now:ans){
            if(check(now.first,now.second,L1[0],L2[0])==true) flag=true;
            if(check(now.first,now.second,L1.back(),L2[0])==true) flag=true;    
        } 
        if(flag==false){
            ask(L1[0],L1.back(),L2.back());
            ans.clear();
            ans.resize(r);
            while(r--) ans[r].first=X[r],ans[r].second=Y[r];
            if(check(ans[0].first,ans[0].second,L1[0],L2.back())==true){
                for(int u:L2) res.push_back(u);
                for(int u:L1) res.push_back(u);
                return res;
            }else{
                reverse(L1.begin(),L1.end());
                for(int u:L2) res.push_back(u);
                for(int u:L1) res.push_back(u);
                return res;
            }
        }else{
            if(check(ans[0].first,ans[0].second,L1[0],L2[0])==true){
                reverse(L2.begin(),L2.end());
                for(int u:L2) res.push_back(u);
                for(int u:L1) res.push_back(u);
                return res;
            }else{
                for(int u:L1) res.push_back(u);
                for(int u:L2) res.push_back(u);
                return res;
            }
        }
    }else{
        if(L1.size()>L2.size()) swap(L1,L2);
        if(L1.size()==1){
            if(L2.size()==1){
                res.push_back(L1[0]);
                res.push_back(cut);
                res.push_back(L2[0]);
                return res;
            }else{
                if(chk(cut,L2[0],L2[1])==true){
                    res.push_back(L1[0]);
                    res.push_back(cut);
                    for(int x:L2) res.push_back(x);
                    return res;
                }else{
                    reverse(L2.begin(),L2.end());
                    res.push_back(L1[0]);
                    res.push_back(cut);
                    for(int x:L2) res.push_back(x);
                    return res;
                }
            }
        }
        if(chk(cut,L1[0],L1[1])==true){
            if(chk(cut,L2[0],L2[1])==true){
                reverse(L2.begin(),L2.end());
                for(int u:L2) res.push_back(u);
                res.push_back(cut);
                for(int u:L1) res.push_back(u);
                return res;
            }else{
                for(int u:L2) res.push_back(u);
                res.push_back(cut);
                for(int u:L1) res.push_back(u);
                return res;
            }
        }else{
            reverse(L1.begin(),L1.end());
            if(chk(cut,L2[0],L2[1])==true){
                reverse(L2.begin(),L2.end());
                for(int u:L2) res.push_back(u);
                res.push_back(cut);
                for(int u:L1) res.push_back(u);
                return res; 
            }else{
                for(int u:L2) res.push_back(u);
                res.push_back(cut);
                for(int u:L1) res.push_back(u);
                return res;
            }
        }
    }
    return res;
}
int p[maxn],x,y;
vector<int> build(){
    for(int i=0;i<n;i++) p[i]=i;
    shuffle(p,p+n,rd);
    x=p[0],y=p[1];
    for(int i=2;i<n;i++){
        if(x==y||x==p[i]||y==p[i]){
            assert(0);
        }
        ask(x,y,p[i]);
        vector< pair<int,int> > ans;
        ans.resize(r);
        while(r--) ans[r].first=X[r],ans[r].second=Y[r];
        if(ans.size()==1&&check(ans[0].first,ans[0].second,x,y)==true) y=p[i];
    }
    vector<int> res;
    vector<int> L1,L2;
    L1.push_back(x);
    L2.push_back(y);
    vector<int> cut;
    for(int i=0;i<n;i++){
        if(i!=x&&i!=y){
            ask(x,y,i);
            vector< pair<int,int> > ans;
            ans.resize(r);
            while(r--) ans[r].first=X[r],ans[r].second=Y[r];
            if(ans.size()==3||(ans.size()==2&&check(ans[0].first,ans[0].second,x,y)!=true&&check(ans[1].first,ans[1].second,x,y)!=true)){
                cut.push_back(i);
            }else if(ans.size()==1){
                if(check(ans[0].first,ans[0].second,x,i)==true) L1.push_back(i);
                else if(check(ans[0].first,ans[0].second,y,i)==true) L2.push_back(i);
                else return res;
            }else return res;
        }
    } 
    while(1){
        vector<int> res=solve(L1);
        if(res.size()==L1.size()){
            L1=res;
            break;
        }
    }
    while(1){
        vector<int> res=solve(L2);
        if(res.size()==L2.size()){
            L2=res;
            break;
        }
    }
    assert(L1.size()==L2.size());
    if(cut.size()==2){
        if(L1.size()==1){
            res.push_back(L1[0]);
            res.push_back(cut[0]);
            res.push_back(L2[0]);
            res.push_back(cut[1]);
            return res;
        }
        if(chk(cut[0],L1[0],L1[1])==true){
            reverse(L1.begin(),L1.end());
            if(chk(cut[0],L2[0],L2[1])==true){
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
                res.push_back(cut[1]);
            }else{
                reverse(L2.begin(),L2.end());
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
                res.push_back(cut[1]);
            }
        }else{
            if(chk(cut[0],L2[0],L2[1])==true){
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
                res.push_back(cut[1]);
            }else{
                reverse(L2.begin(),L2.end());
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
                res.push_back(cut[1]);
            }
        }
        return res;
    }else if(cut.size()==1){
        if(L1.size()==1){
            res.push_back(L1[0]);
            res.push_back(cut[0]);
            res.push_back(L2[0]);
            return res;
        }
        if(chk(cut[0],L1[0],L1[1])==true){
            reverse(L1.begin(),L1.end());
            if(chk(cut[0],L2[0],L2[1])==true){
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
            }else{
                reverse(L2.begin(),L2.end());
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
            }
        }else{
            if(chk(cut[0],L2[0],L2[1])==true){
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
            }else{
                reverse(L2.begin(),L2.end());
                for(int x:L1) res.push_back(x);
                res.push_back(cut[0]);
                for(int x:L2) res.push_back(x);
            }
        }
        return res;
    }else{
        if(L1.size()==1){
            res.push_back(L1[0]);
            res.push_back(L2[0]);
            return res;
        }
        ask(L1[0],L1.back(),L2[0]);
        vector< pair<int,int> > ans;
        ans.resize(r);
        while(r--) ans[r].first=X[r],ans[r].second=Y[r];
        for(pair<int,int> now:ans){
            if(check(now.first,now.second,L2[0],L1[0])==true){
                reverse(L1.begin(),L1.end());
                for(int x:L1) res.push_back(x);
                for(int x:L2) res.push_back(x);
                return res;
            }
            if(check(now.first,now.second,L2[0],L1.back())==true){
                for(int x:L1) res.push_back(x);
                for(int x:L2) res.push_back(x);
                return res; 
            }
        }
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t,k;
    cin>>t>>k;
    for(int i=1;i<=t;i++){
        cin>>n;
        while(1){
            vector<int> res=build();
            if(res.size()==n){
                cout<<"! ";
                for(int i=0;i<n;i++){
                    cout<<res[i];
                    if(i!=n-1) cout<<" ";
                }
                cout<<endl;
                break;
            }
        }
        for(int j=0;j<n;j++) dp[j].clear();
    }
    return 0;
}