题解：P10440 [JOIST 2024] 环岛旅行 / Island Hopping

reinforest · 2025-09-28 20:53:58 · 题解

考虑以 1 为根。

如果确定了 i=1，令 k 取遍 [1,n-1]，那么最后的答案一定是从 1 开始的 bfs 序。

一个比较好的想法是确定每一个点的父亲。

考虑 bfs 序与一个点的父亲有什么性质。可以发现“u 是 v 的父亲”是“u 的 bfs 序在 v 之前”的充分不必要条件。

考虑什么时候它必要。当然，如果 u 和 v 相邻，那么它一定是必要的。

所以可以从 2 号点往后依次确定父亲了。考虑当前搜到的是点 i：

• 如果 i 号点的父亲已经被确定了就跳过；

• 否则，从小到大取遍 k \in [1,n-1]，直到能够确定 i 号点的父亲为止，即 query(i,k) 得到的 bfs 序比 i 号点的 bfs 序要小。可以证明，跳出循环之前搜到的点一定与 i 相邻。

• 对于失败的点，实际上可以确定 i 是这些点的父亲。很简单，因为此时这些点的 bfs 序大于 i 的 bfs 序。

所以每一个父亲-儿子关系只会查询有且仅有一次，查询的次数为确定 bfs 序与确定父亲-儿子关系的查询次数之和 2n-2，可以通过。

#include<bits/stdc++.h>
using namespace std;
int query(int,int);
void answer(int,int);
int main();
int fa[1005],bfn[1005],nfb[1005];
void solve(int N,int L){
    for(int i=1;i<=N-1;i++){
        int x=query(1,i);
        bfn[x]=i;
        nfb[i]=x;
    }
    for(int i=1;i<=N-1;i++){
        if(fa[nfb[i]])continue;
        for(int k=1;k<=N-1;k++){
            int x=query(nfb[i],k);
            if(bfn[x]<i){
                fa[nfb[i]]=x;
                break;
            }else{
                fa[x]=nfb[i];
            }
        }
    }
    for(int i=2;i<=N;i++){
        answer(fa[i],i);
    }
}
// int query(int v,int k){
//     cout<<"? "<<v<<" "<<k<<"\n";
//     int x;
//     cin>>x;
//     return x;
// }
// void answer(int x,int y){
//     cout<<"! "<<x<<" "<<y<<"\n";
// }
// int main(){
//     int N,L;
//     cin>>N>>L;
//     solve(N,L);
//     return 0;
// }