cojs 简单的区间问题 解题报告

时间:2021-07-18 05:00:31

新学了些弦图和区间图的新玩意,于是就想着出一道题目

其实这道题不用弦图和区间图的理论也是可以做的

首先考虑第一问,第一问是一个NOIP普及组水平的贪心

我们把区间按照右端点从小到大排序,之后从头到尾扫一遍,能取就取即可

有关于贪心的正确性的证明是很简单的:

首先我们考虑后面的区间和当前的区间的关系

1、后面的区间包含当前的区间,显然取当前区间比后面的区间要优

2、后面的区间k和当前的区间相交,设k后面的区间为j

则一定有若j和当前的区间有重叠部分,则j一定和k有重叠部分

反之则不一定,由于两个区间只能取一个,所以取当前区间比取k优

3、后面的区间和当前区间不相交,则当前区间对其无影响,选了总比不选好

之后我们考虑用区间图的思路去解决这道题目

显然在有重叠部分的区间之间建边,得到的图是一个弦图

我们用MCS将弦图的完美消除序列搞出来,之后这个问题就变成了弦图的最大独立集

又因为区间图的特性,所以将区间按右端点从小到大排序,得到的序列就是区间图的完美消除序列

这样做法就跟上面的贪心一模一样了

(本来想区间带权的,结果考虑到还有第二问就没有出)

之后我们考虑第二问,我们用一发dilworth定理之后就发现这个问题实际上几乎和第一问是一样的

按右端点从大到小排序贪心即可

我们考虑用区间图的思路去解决这道题目

这显然就是弦图的染色问题,我们逆序扫完美消除序列给每个点染能染的最小颜色

答案就是每个点颜色的最大值

(口胡一句:dilworth一发之后就是求最大团了!)

由于本人太傻,对于这一部分只能写n^2的算法

所以只出到了n<=10000的范围

不知道有没有神犇可以优化一下,把n调到10w QAQ