不限时OA求助

ymmmmm 发表于 2022-2-12 08:20
谢谢你的回答！我按照你的方法写了一遍 把2个TLE中的一个过了。还有一个TLE是有很多个点，但是只有一个sp ...

对于最后一个tle，尝试把所有点按照x坐标排序，在枚举j点找与i点毗邻的点时，用二分查找找出哪些点j满足x[i]-r<=x[j]<=x[i]+r。仅在这些点中搜索，若数据非带状密集分布，平均时间复杂度大概为O(nlogn）而非O(n^2)。
BFS剪枝：在BFS过程中，AI每跳转到一个新点就把这个点标记为可跳转，并在新点上继续跳转。如若AI要跳转的下一个点已经被标记了，这说明自己或者其他的AI已经跳转过这个点了，因此可以把这个点及其后续的路径在搜索树上删除。这就是剪枝。剪枝后可以保证每个可跳转点有且只有一次被跳转，复杂度O(n)

listerily 发表于 2022-2-11 20:04
对于最后一个tle，尝试把所有点按照x坐标排序，在枚举j点找与i点毗邻的点时，用二分查找找出哪些点j满足x ...

我已经进行了二分查找区间优化了 还是TLE。真不懂了 方便私信你code帮我看看吗。关于剪枝，你的意思是DFS然后维护一个visited set。如果visited过就pass掉吗？

ymmmmm 发表于 2022-2-12 12:53
我已经进行了二分查找区间优化了 还是TLE。真不懂了 方便私信你code帮我看看吗。关于剪枝，你的意思是DFS ...

可以（但这也tle我可能也没啥办法了）。是。

不需要bfs，只要并查集就可以了。找一个带路径压缩的并查集代码。

1.把距离小于r的两个点union。
大致思路是x轴方向分组，y方向排序，应该可以做到NlogN。
例如把点按照横坐标丢到桶里[0, r)[r, 2r)。 对每个点只需要检查当前组，左边的组，右边的组里y值绝对值差不大于r的点。

2.把spawner跟虚点0 union（O N）
3.检查每一个点是否与虚点0联通。(O N)

如果还是TLE就是第一步写的不够好。

ymmmmm 发表于 2022-2-12 12:53
我已经进行了二分查找区间优化了 还是TLE。真不懂了 方便私信你code帮我看看吗。关于剪枝，你的意思是DFS ...

看了您的代码，感觉没大问题。还可以进行一个小优化就是令leftBound=max(leftBound, i + 1)。因为可跳转关系满足对称性，我们对于点i只需要知道j>i的可跳转点就行，这样能减去一半的搜索。
还可以采用zjudky的“x分组y排序”的方法，应该会比我的方法要好一些。
另外，二分查找可以使用lower_bound和upper_bound。

listerily 发表于 2022-2-12 02:08
看了您的代码，感觉没大问题。还可以进行一个小优化就是令leftBound=max(leftBound, i + 1)。因为可跳转 ...

用x分组y排序的方法做出来了。 谢谢大佬的引导！

bydstand 发表于 2022-2-11 21:50
不需要bfs，只要并查集就可以了。找一个带路径压缩的并查集代码。

1.把距离小于r的两个点union。

用您的方法做出来了！ 谢谢！