专栏文章

题解：P2632 Explorer

FFirsry
P2632题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miov0pnm
此快照首次捕获于
2025/12/03 01:36
3 个月前
此快照最后确认于
2025/12/03 01:36
3 个月前
查看原文

人类智慧

蒟蒻太弱了，准高二了还不会用直线解析式算垂足，所以就用玄学连边 A 了。
注意到主要矛盾是优化建边，边的数量又是 Kruskal 的命根子，所以我们只连可能比较有用的边。
观察到两条直线 l1,l2l_1, l_2，l1l_1 上面的点在 l2l_2 上的垂足是有单调性的，所以充分发扬人类智慧，设置大小为 108108 的观察窗口以及大小为 1515 的连边窗口，用于找到最优点，并且在最优点附近（可能有用的点）进行连边。

细节处理

  • 为了保证从一端看向另一端，我们需要 sort 一下 t 数组；
  • Kruskal 一定是连成一棵树之后 edgeCount = n + m - 1 就 break；
  • 时间空间都很极限，我们的匹配点 match 从数组优化为两个滚动变量 pre, match；
  • 观察需要比较大，但是连边不是；（本蒟蒻大量的 MLE 来自这一点没有考虑到 qwq）
  • double 保证高精，不要管为什么 #define dwb double，因为是彩蛋；
upd：AddRange = 5, SeeRange = 50 既可通过此题，更多的极限数据测试已经没脸再交了 qwq。
代码如下：
CPP
#include<bits/stdc++.h>
#define dwb double

using namespace std;

const int AddRange = 15;
const int SeeRange = 108;

const int MAXN = 100055;
const dwb INF = 1e18;

struct Edge {
	int from, to;
	dwb weight;
	bool operator < (const Edge another) const {
		return weight < another.weight;
	}
};

int n, m;
int px[5], py[5];
dwb t1[MAXN], t2[MAXN];
dwb x1_, y1_, x2_, y2_;

int anc[MAXN << 1];

vector<Edge> edge;

inline void AncInit(int siz) {
	for (int i = 1; i <= siz; ++i)
		anc[i] = i;
	return;
}
inline int findAnc(int cur) {
	if (cur != anc[cur])
		anc[cur] = findAnc(anc[cur]);
	return anc[cur];
}
inline void merge(int a, int b) {
	anc[findAnc(a)] = findAnc(b);
}

inline dwb calX(dwb t, int p1, int p2) {
	return px[p1] * t + px[p2] * (1 - t);
}
inline dwb calY(dwb t, int p1, int p2) {
	return py[p1] * t + py[p2] * (1 - t);
}
inline dwb calDis() {
	return sqrt((x1_ - x2_) * (x1_ - x2_) + (y1_ - y2_) * (y1_ - y2_));
}

inline void kruskal() {
	dwb mst = 0;
	sort(edge.begin(), edge.end());
	AncInit(n + m);
	int edgeCount = 0, aim = n + m - 1;
	for (Edge e : edge) {
		int ancFrom = findAnc(e.from);
		int ancTo = findAnc(e.to);
		if (ancFrom != ancTo) {
			merge(ancFrom, ancTo);
			mst += e.weight;
			edgeCount++;
			if (edgeCount == aim)
				break;
		}
	}
	printf("%.3lf", mst);
}

inline void init() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= 4; ++i)
		scanf("%d%d", &px[i], &py[i]);
	for (int i = 1; i <= n; ++i)
		scanf("%lf", &t1[i]);
	for (int i = 1; i <= m; ++i)
		scanf("%lf", &t2[i]);

	sort(t1 + 1, t1 + 1 + n);
	sort(t2 + 1, t2 + 1 + m);

	for (int i = 2; i <= n; ++i) {
		x1_ = calX(t1[i - 1], 1, 2);
		y1_ = calY(t1[i - 1], 1, 2);
		x2_ = calX(t1[i], 1, 2);
		y2_ = calY(t1[i], 1, 2);
		edge.push_back({i - 1, i, calDis()});
	}
	for (int i = 2; i <= m; ++i) {
		x1_ = calX(t2[i - 1], 3, 4);
		y1_ = calY(t2[i - 1], 3, 4);
		x2_ = calX(t2[i], 3, 4);
		y2_ = calY(t2[i], 3, 4);
		edge.push_back({i - 1 + n, i + n, calDis()});
	}
}

inline void build() {
	int pre = 1, st = 1, ed = m;
	for (int i = 1; i <= n; ++i) {
		x1_ = calX(t1[i], 1, 2);
		y1_ = calY(t1[i], 1, 2);
		if (i != 1) {
			st = max(1, pre - SeeRange);
			ed = min(m, pre + SeeRange);
		}
		dwb minDis = INF;
		int match = st;
		for (int j = st; j <= ed; ++j) {
			x2_ = calX(t2[j], 3, 4);
			y2_ = calY(t2[j], 3, 4);
			dwb dis = calDis();
			if (dis < minDis)
				minDis = dis, match = j;
		}
		pre = match;
		int add_st = max(1, match - AddRange);
		int add_ed = min(m, match + AddRange);
		for (int j = add_st; j <= add_ed; ++j) {
			x2_ = calX(t2[j], 3, 4);
			y2_ = calY(t2[j], 3, 4);
			edge.push_back({i, j + n, calDis()});
		}
	}
}

int main() {
	init();
	build();
	kruskal();
	return 0;
}

评论

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

正在加载评论...