2024.10.3 题目

题解：2024.10.3 模拟赛

旋律的总数

数学

给定 $n,m$，需要构建长度为 $n$ 的不同序列 $a$。定义满足 $a_i\equiv b_i+k(\mathrm{mod}m)$ 的序列 $a,b$ 为相等的序列，求满足条件的 $a$ 的数量，对 $10^9+7$ 取模。

水果加工

序列dp 二分

有 $n$ 片果园，第 $i$ 片果园种着 $a_i$ 吨水果。有两个加工基地，需要将 $n$ 片果园的所有水果运到加工基地加工。从第 $j$ 片果园运到第 $i$ 的基地的时间为每吨 $d_{i,j}$ 小时。第 $i$ 个基地有 $b_i$ 台机器，需要 $c_{i,j}$ 台机器组装生产线加工第 $j$ 片果园的水果，加工速度为每吨 $u_{i,j}$ 小时。一个果园的水果可以分别运到不同的加工基地。当所有水果运送完之后会同时开始加工。求运输加加工的最小时间。

最佳位置

贪心 平衡树

有 $n$ 个座位，会有 $m$ 个人按照顺序进来。令 $f_i$ 表示为离 $i$ 最近的被占用的座位 $j$ 离 $i$ 的距离。新来的人会选择最小 $f_i$ 的 $i$，如果有多个选择最小的 $i$，在 $i$ 位置上落座。有的人会在中途离开，空出位置。你需要输出每个人落座时会选择什么位置。

跑步路线

生成树 最近公共祖先 图 树 树形dp 倍增

有 $n$ 点 $m$ 边的连通图，第 $i$ 条边连接 $(u_i,v_i)$，花费时间为 $w_i$。规定长度为 $k$ 的路径 $a$，要按照顺序一个个经过结点 $a_i$（$a_i$ 可能重复）。经过的路线必须在图的最小生成树上，且除了起始结点与终点结点外，每个经过的结点都要额外增加 $t_0$ 的时间。问你最短时间的合法路线的时间是多少。