关于暴力lca为什么这么快
  • 板块学术版
  • 楼主JoeBiden2020
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/11/21 11:53
  • 上次更新2023/11/3 23:51:23
查看原帖
关于暴力lca为什么这么快
432183
JoeBiden2020楼主2021/11/21 11:53

自己出了一道题,数据范围 n3×104n\le3\times 10^4。我对于每个节点随机与比它小的节点连边,为了加大深度,限制每节点出度不能超过2,结果

暴力跳:最慢点 17ms,1.24Mib

倍增:最慢点 28ms,3.66Mib

树剖:最慢点 44ms,7.22Mib

?????

什么鬼???

更别提模板题目 5×1055\times 10^5 的范围,数据没加强之前最优解是暴力。。。

有大佬来解释一下吗,O(n2)O(n^2) 怎么可能跑过三万的随机数据

2021/11/21 11:53
加载中...