2024.11.17 题目

总结：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)$ 有多少未被覆盖。