题解：P11423 [清华集训 2024] 阿尔塔尔 2

· · 题解

很容易发现竞赛图中一定能找到一个点到其余点的距离 \le 2，也就是说最终图的第 0 层与第 1 层的点会形成菊花，而第 1 层的点与其所管的第 2 的点同样也会形成菊花。

我们考虑增量维护前两层的结构。对于新加的点 x，先访问第一层的点，若存在一个点连向 x 则可以直接加入进这个点的管辖集合。否则我们询问 x 与 rt 的连边，若 rt\to x 则将 x 加入第一层，否则让 x 成为 rt，而 rt 成为第一层的点。

考虑上述做法可能会让第一层点很多，于是我们稍微优化一下：当一个点要被放进第一层时，我们考虑它是否有独属于它的后继结点，若没有我们就可以不放进第一层。这个做法的正确性在于它是 rt 独属的后继结点，也就是保证了 rt 一定至少是第一层的点，这样就能保证最终 rt 到它的距离 \le 2。

由于交互库并非自适应，于是随一个排列之后期望平均询问次数 \le 2n。可以通过。

代码：

#include <bits/stdc++.h>
#include"altar.h"
using namespace std;
const int N=305;
bool sense(int i, int j);
int p[N],vis[N];
mt19937 orz(random_device{}());
int altar(int n){
    for(int i = 1;i<=n;i++)p[i]=i,vis[i]=0;
    shuffle(p+1,p+n+1,orz);
    int rt = p[1];
    vector<int>v;
    for(int i = 2;i<=n;i++){
        for(auto j : v)if(sense(j,p[i])){
            goto ed;
        }
        if(sense(rt,p[i]))vis[rt]=1;
        else{
            if(vis[rt])v.push_back(rt);
            else vis[p[i]]=1;
            rt=p[i];
        }
        ed:;
    }
    return rt;
}