【学习笔记】「JOISC 2017 Day 3」自然公园-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学习笔记】「JOISC 2017 Day 3」自然公园。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

考虑对于一个点 $x$ ，找到它与当前连通块相连的所有边。我们希望通过 $\log n$ 次询问确定一条边。

一般的策略是将数划分成两个大小相同集合然后去找答案，这里考虑 二分前缀，因为将点按照 $D FN$ 序排序，可以保证这段前缀构成一个连通块。那么固定根节点 $r$ ，询问 $x$ 和 $r$ 是否可达，找到最小的前缀 $y$ ，就能确定 $x$ 和 $y$ 之间有一条边。将 $y$ 删掉后处理剩下的连通块即可，这部分有 $m\log n$ 次。

然后考虑怎么确定 $x$ 。发现可以通过类似的方法确定从 $x$ 到连通块的路径上的一个点 $y$ ，那么先递归处理 $y$ ，直到不存在这样的 $y$ 时再把 $x$ 加入连通块即可。注意到每个节点只会被找到一次，这部分复杂度 $n\log n$ 。

总次数 $(n+m)\log n$ 。文章来源地址https://www.toymoban.com/news/detail-705795.html

#include<bits/stdc++.h>
#include "park.h"
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
mt19937 gen(114514);
int vs[1405],vs2[1405],state[1405],n;
vector<int>nums;
vector<int>G[1405];
void dfs(int u,int topf){
    nums.pb(u);
    for(auto v:G[u]){
        if(v==topf||vs2[v])continue;
        dfs(v,u);
    }
}
int work(int p,int rt){
    nums.clear(),dfs(rt,-1);
    memset(vs,0,sizeof vs);
    for(auto e:nums)vs[e]=1;vs[p]=1;
    if(Ask(min(p,rt),max(p,rt),vs)==0)return -1;
    int l=1,r=nums.size(),res=0;
    while(l<=r){
        int mid=l+r>>1;
        memset(vs,0,sizeof vs);
        for(int i=0;i<mid;i++)vs[nums[i]]=1;vs[p]=1;
        if(Ask(min(p,rt),max(p,rt),vs))res=mid,r=mid-1;
        else l=mid+1;
    }
    int tmp=nums[res-1];vs2[tmp]=1;
    Answer(min(p,tmp),max(p,tmp));
    for(auto u:G[tmp]){
        if(vs2[u]==0)work(p,u);
    }return tmp;
}
int get(int x){
    int l=1,r=n,res=0;
    while(l<=r){
        int mid=l+r>>1;
        for(int i=0;i<mid;i++){
            vs[i]=(state[i]==1||state[i]==0);
        }
        for(int i=mid;i<n;i++){
            vs[i]=(state[i]==1);
        }
        vs[x]=1;
        if(Ask(0,x,vs)){
            res=mid,r=mid-1;
        }
        else{
            l=mid+1;
        }
    }return res-1;
}
void solve(int x){
    state[x]=2;int y;
    while(1){
        memset(vs2,0,sizeof vs2);
        y=work(x,0);
        if(~y){
            state[x]=1;
            G[x].pb(y),G[y].pb(x);
            return;
        }
        solve(get(x));
    }
}
void Detect(int T,int N){
    n=N;
    state[0]=1;
    for(int i=1;i<n;i++){
        if(state[i]==0)solve(i);
    }
}