贪心

CF960C Subsequence Counting

Pikachu had an array with him. He wrote down all the non-empty subsequences of the array on paper. Note that an array of size n has 2n - 1 non-empty subsequences in it. Pikachu being mischievous as he always is, removed all the subsequences in which Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ d Pikachu was finally left with X subsequences. However, he lost the initial array he had, and now is in serious trouble. He still remembers the numbers X and d. He now wants you to construct any such array which will satisfy the above conditions. All the numbers in the final array should be positive integers less than 1018. Note the number of elements in the output array should not be more than 104. If no answer is possible, print  - 1. (更多…)

DefFrancis
数据结构

[NOI2016]区间

P1712 [NOI2016]区间

题目描述

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间,使得这 m个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri。 对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li,即等于它的右端点的值减去左端点的值。 求所有合法方案中最小的花费。如果不存在合法的方案,输出 −1。 (更多…)

DefFrancis