Luogu分析首先容易看出一个暴力,即每个点向能到达的点连边,然后最短路即可。然而边数是 $\mathcal{O}(n^2)$ 级别的,我们需要优化连边。由于是向矩形范围内的点连边,所以考虑 KD-Tree 优化连边。对于城市 $u$ 向矩形连的边,我们在 KD-Tree 上遍历:如果当前节点范围包含在矩形内,则 $u$ 直接向这个节点连边;如果当前节点范围与矩形无交,则直接返回;否则,如果...
LuoguLOJ分析暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。考虑用 KD-Tree 优化模拟过程。我们把每个圆看作它的外接矩形,然后对于当前删去的圆在 KD-Tree 上递归,如果圆与矩形没有交则不会更新,可以直接返回。然后建树时按方差选维度就可以过了。代码// =================================== // author: ...
LuoguLOJ分析暴力就是维护一个大小为 $k$ 的小根堆,然后 $\mathcal{O}(n^2)$ 枚举。考虑用 KD-Tree 优化。对于每个点在 KD-Tree 上递归,如果当当前矩形的最大距离比堆顶小则不可能更新答案,可以直接返回。因为是每对点算了两遍所以堆的大小应为 $2k$,为了方便可以先插 $2k$ 个 $0$ 进去。代码// =======================...
Luogu分析还是 KD-Tree 板子。插入时利用替罪羊树重构那一套保证平衡。查询时判断查询矩形和当前矩形是否有交,如果完全包含直接返回当前矩形和,部分包含就递归下去,否则返回 $0$。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ===...
Luogu分析KD-Tree 板子。插入时可能会让 KDT 不平衡,用类似于替罪羊树的方式定期重构即可。查询时利用到矩形的最短距离剪枝。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =============================...