题意 题目链接。 给定一个长度为 $n$ 的环，有 $k$ 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。 解析 先考虑如果是链的话就是一个朴素的贪心：每次在所有左端点不大于当前位置的点中选取一个右端点最大的跳过去。对于环，容易想到将其断开，在其后面复制一份即可。 问题转化为了一个长度为 $2n$ 的链，求最少数量的区域使其能够覆盖长度至少为 …

为什么这么裸的题是紫题。 题意 题目链接 注意权值最小值指的是这 $k$ 条边中权值最小的那条边的值就好，题意叙述的很清楚了。另外注意点号是从 $0$ 开始的。 解析 一看数据范围, $1 \le k \le 10^{10}$ ,很显然正常跑跑不了，既然要快速跑，而本题中又没有对边的权值进行改变，再给了每个点有且仅有一条出边，很容易就能想到倍增。 …