3602专题

#贪心,平衡树#洛谷 3602 Koishi Loves Segments

题目 有 n n n个区间,有 m m m个限制,第 i i i个点不得覆盖超过 t i t_i ti​个区间,问最多能保留多少个区间 分析 首先对于每个限制进行排序,那按照贪心的思想,首先对区间的开头进行排序,那首先之前没有限制的区间可以删掉了,然后如果不满足,区间的末尾越大,越值得删掉,因为这个区间很有可能继续受到影响,那就是平衡树了,但是我太菜了,只会multiset,时间复杂度

LA - 3602 - DNA Consensus String

题意:有m个长度为n的ACGT序列,求一个长度为n的序列,使得每一位与这m个序列相应位的距离和最小(相同为0,不同为1)(4 <= m <= 50, 4 <= n <= 1000)。 题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&categor