主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
【题解】ひかり(hikari)
最后更新于 2025-07-31 09:39:39
作者
奇犽
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
## ひかり(hikari) ### $O(n^3)$ 将所有灯塔按 $x_i$排序 枚举两个灯塔 $i,j$ 再枚举 $i,j$ 之间的灯塔 $k$ ,判断 $i,j$ 连线是否会穿过 $k$ 灯塔，若 $(i,j)$ 合法，概率增加 $ p_i * p_j * ny(n*(n-1))$ ### $O(n^2)$ 凸包思想 将所有灯塔按 $x_i$排序 枚举一个个灯塔 $i$ 再枚举 $i$ 之前的灯塔 $j$ ,判断 $j$ 是否能产生贡献，对于 $j,i$ 之间的灯塔,进行叉积判断。 ## ひかり(hikari) 加强版 ### $O(m^2)$ 同上述$O(n^2)$做法，对于每个窗子进行判断。 ### $O(nm\log_2 m)$ 对于在同一栋楼，进行二分，其余同上
正在渲染内容...
点赞
0
收藏
0
