acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 「POI2010」灯 Lamp 题解

    直接说难点和注意事项: 开区间处理:窗户是开矩形,光线在边界上被吸收。代码中使用 X1 + EPS < X2 等严格不等式判断交集,确保边界点不会被错误计入。 浮点精度:使用 EPS = 1E-12 处理浮点比较,避免因精度问题导致的误判。 集合爆炸:每次迭代矩形数量可能增长,代码设置了 MAX_RECTS = 200000 作为上限,防止内存溢出。实际数据中矩形数量不会达到此上限。 反射次数上限:T_MAX = 2000 足以覆盖所有有效光路。随着反射次数增加,等效距离变大,区域会迅速收缩,更多次反射不会产生新的有效路径。 CODE: 时间复杂度:O(T×R×600)O(T × R × 600)O(T×R×600)(最坏)(当然实际运行中,由于区域不断收缩,R保持在较小水平,远优于理论最坏情况) 空间复杂度:O(R)O(R)O(R)

    userId_undefined
    码农爱历史
    7月全勤卷王出道萌新时空双修者荣耀黄金快乐小狗造物者
    8阅读
    1回复
    1点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页