社区讨论
【脑洞】本题升级版
P3357最长k可重线段集问题参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi7pundj
- 此快照首次捕获于
- 2025/11/21 01:39 4 个月前
- 此快照最后确认于
- 2025/11/21 01:39 4 个月前
话说那区间是一维,线段是二维,拍扁了降维,然后考虑一维。
如果我们再加一维。变成一个三维空间中的线段。
对于给定空间中n个开线段组成的集合,和一个正整数。试设计一个算法,从开线段集合中选取出开线段集合,使得空间内任何一个平面,
中与平面相交的开线段个数不超过,且达到最大。
这样的集合称为开线段集合的最长可重线段集。称为最长可重线段集的长度。
求长度。
数据范围
,
坐标全部不超过50且不存在负数
(保证数据中不存在线段与平面共面的情况~~(不会告诉你们我被坑过)~~)
似乎还是把三维拍扁。只考虑x坐标,然后照常跑。(这样不还是一道题吗???)
那么如果不保证数据中不存在线段与平面共面的情况
得出结论,此题单纯增加维度是无意义的,限制条件为
时只需考虑坐标和特判一些垂直共面的情况。
那么胡搞瞎搞的下一步是改变条件。
给定一个线段集,使得选出子集与线段集相交的线段个数不超过。
有人有比较优秀的观点吗,期待分享。
回复
共 2 条回复,欢迎继续交流。
正在加载回复...