总结：[[2024.11.17 模拟赛]] ## 覆盖 #排序 #二分 #贪心 坐标轴上有 $n$ 个区间，每个区间均在左端点为 $0$，右端点为 $w$ 的线段内。第 $i$ 个区间的左右端点表示的数字分别为 $l_i$ 和 $r_1$。 现在你要去掉一部分区间，使得有一段长度为 $c$ 的线段没有被任何区间覆盖。第 $i$ 个区间删去的代价为 $p_i$。请输出你所花费的最小代价。 ## 分发传单 B 公司使用机器人分发传单，机器人需要在接下来 $n$ 秒的时间内分发尽可能多的传单。 一开始，B 公司拥有一个型号为 $bot-1$ 的机器人，解下来的 $n$ 秒时间内，型号为 $bot-i$ 的机器人可以进行如下操作： - 花费 $1$ 秒的时间，分发一张传单。 - 花费 $c\times i$ 秒的时间，生成一个型号为 $bot-(i+1)$ 的机器人。其中  是一个给定常数。 每一个机器人的每种操作都可以多次进行。 机器人可以计算出最优策略，在 $n$ 秒的时间内，分发出最多的传单。 请求出最多分发的传单数，因为答案可能很大，输出答案对 $10^9+7$ 取模的结果。 因为现实中的情况是多变的，B 公司希望对 $q$ 组的 $n_i,c_i$ 分别求出答案。 ## 绘画 小 C 有一张 $1\times n$ 的白纸条，被划分为了 $n$ 个单元格。 小 C 会进行 $k$ 次绘画，第 $i$ 次会将连续的恰好 $a_i$ 个单元格染黑，如果一个单元格已经被染黑则颜色不变。 请问小 C 进行 $k$ 次绘画后，可能得到多少种不同的纸条？ 输出不同的纸条数对 $10^9+7$ 取模的结果，两个纸条不同当且仅当至少存在一个 $x$ 满足第 $x$ 个单元格在两个纸条中的颜色不同。 ## 三角覆盖 给出一个直角边长为 $n$ 的等腰直角三角形点集，共有 $n$ 行，第 $i$ 行的点为 $(i,1),(i,2),\cdots,(i,i)$。 有 $m$ 次覆盖操作，每次覆盖一个等腰直角三角形区域内的点，第 $i$ 次给出 $3$ 个数 $a_i,b_i,c_i$，表示对于 $1\le k\le j\le c_i$，点 $(a_i+j-1,b_i+k-1)$ 被覆盖了。 随后给出 $q$ 次询问操作，询问一个等腰直角三角形区域内未被覆盖的点数，第 $i$ 次给出 $3$ 个数 $d_i,e_i,f_i$，表示询问所有 $1\le k\le j\le f$，点 $(d_i+j-1,e_i+k-1)$ 有多少未被覆盖。