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

考虑以

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

，可以通过。

CPP

#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;
// }

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

文章操作

相关推荐

评论

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