社区讨论

【脑洞】本题升级版

P3357最长k可重线段集问题参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7pundj
此快照首次捕获于
2025/11/21 01:39
4 个月前
此快照最后确认于
2025/11/21 01:39
4 个月前
查看原帖
话说那区间是一维,线段是二维,拍扁了降维,然后考虑一维。
如果我们再加一维。变成一个三维空间中的线段。
对于给定空间中n个开线段组成的集合II,和一个正整数kk。试设计一个算法,从开线段集合II中选取出开线段集合SIS⊆I,使得空间内任何一个平面x=px=pSS中与平面x=px=p相交的开线段个数不超过kk,且z(zs)∑|z|(z⊆s)达到最大。 这样的集合SS称为开线段集合II的最长kk可重线段集。z(zs)∑|z|(z⊆s)称为最长kk可重线段集的长度。 求长度。
数据范围
1n1001≤n≤100, 1k101≤k≤10
坐标全部不超过50且不存在负数
(保证数据中不存在线段与平面x=px=p共面的情况~~(不会告诉你们我被坑过)~~)
(昨晚睡前想到了三维偏序和cdq分治)
似乎还是把三维拍扁。只考虑x坐标,然后照常跑。(这样不还是一道题吗???)
那么如果不保证数据中不存在线段与平面x=px=p共面的情况
(为什么感觉还是同一道题)
得出结论,此题单纯增加维度是无意义的,限制条件为 x=px=p时只需考虑xx坐标和特判一些垂直共面的情况。
那么胡搞瞎搞的下一步是改变条件。
给定一个线段集LL,使得选出子集SS与线段集相交的线段个数不超过kk
有人有比较优秀的观点吗,期待分享。

回复

2 条回复,欢迎继续交流。

正在加载回复...