洛谷5471 [NOI2019]弹跳
Luogu 分析 首先容易看出一个暴力，即每个点向能到达的点连边，然后最短路即可。 然而边数是 $\mathcal{O}(n^2)$ 级别的，我们需要优化连边。由于是向矩形范围内的点连边，所以考虑 KD-Tree 优化连边。 对于城市 $u$ 向矩形连的边，我们在 KD-Tree 上遍历：如果当前节点范围包含在矩形内，则 $u$ 直接向这个节点连边；如果当前节点范围与矩形无交，则直接返回；否...
Luogu 分析 首先容易看出一个暴力，即每个点向能到达的点连边，然后最短路即可。 然而边数是 $\mathcal{O}(n^2)$ 级别的，我们需要优化连边。由于是向矩形范围内的点连边，所以考虑 KD-Tree 优化连边。 对于城市 $u$ 向矩形连的边，我们在 KD-Tree 上遍历：如果当前节点范围包含在矩形内，则 $u$ 直接向这个节点连边；如果当前节点范围与矩形无交，则直接返回；否...
Luogu LOJ 分析 暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。 考虑用 KD-Tree 优化模拟过程。 我们把每个圆看作它的外接矩形，然后对于当前删去的圆在 KD-Tree 上递归，如果圆与矩形没有交则不会更新，可以直接返回。 然后建树时按方差选维度就可以过了。 代码 // =================================== // ...