专栏文章

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

居居然有个高手
P11423题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mippr23p
此快照首次捕获于
2025/12/03 15:56
3 个月前
此快照最后确认于
2025/12/03 15:56
3 个月前
查看原文
很容易发现竞赛图中一定能找到一个点到其余点的距离 ≤2\le 2，也就是说最终图的第 00 层与第 11 层的点会形成菊花，而第 11 层的点与其所管的第 22 的点同样也会形成菊花。
我们考虑增量维护前两层的结构。对于新加的点 xx，先访问第一层的点，若存在一个点连向 xx 则可以直接加入进这个点的管辖集合。否则我们询问 xx 与 rtrt 的连边，若 rt→xrt\to x 则将 xx 加入第一层，否则让 xx 成为 rtrt，而 rtrt 成为第一层的点。
考虑上述做法可能会让第一层点很多，于是我们稍微优化一下：当一个点要被放进第一层时，我们考虑它是否有独属于它的后继结点，若没有我们就可以不放进第一层。这个做法的正确性在于它是 rtrt 独属的后继结点，也就是保证了 rtrt 一定至少是第一层的点，这样就能保证最终 rtrt 到它的距离 ≤2\le 2。
由于交互库并非自适应，于是随一个排列之后期望平均询问次数 ≤2n\le 2n。可以通过。
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...