题目：[[2024.10.3 题目]] ## 旋律的总数 给定 $n,m$，需要构建长度为 $n$ 的不同序列 $a$。定义满足 $a_i\equiv b_i+k\pmod m$ 的序列 $a,b$ 为相等的序列，求满足条件的 $a$ 的数量，对 $10^9+7$ 取模。 --- 首先，我们考虑没有限制的情况下有多少种选择方式。不难发现，每个音符有 $m$ 种选择，需要选择 $n$ 个音符，因此选择数量有 $m^n$ 种。由于 $\bmod m$ 可能会出现 $0\sim m-1$ 共 $m$ 种情况，因此一种本质不同的旋律可以引申出另外 $m-1$ 种旋律，所以将 $m^n$ 除以 $m$ 即可，也便是 $m^{n-1}$。 ## 水果加工 有 $n$ 片果园，第 $i$ 片果园种着 $a_i$ 吨水果。有两个加工基地，需要将 $n$ 片果园的所有水果运到加工基地加工。从第 $j$ 片果园运到第 $i$ 的基地的时间为每吨 $d_{i,j}$ 小时。第 $i$ 个基地有 $b_i$ 台机器，需要 $c_{i,j}$ 台机器组装生产线加工第 $j$ 片果园的水果，加工速度为每吨 $u_{i,j}$ 小时。一个果园的水果可以分别运到不同的加工基地。当所有水果运送完之后会同时开始加工。求运输加加工的最小时间。 --- 使用序列 dp。令 $dp_{i,j,k,l,0/1}$ 表示为已经处理了 $i$ 个果园，第 $i$ 个果园对第一个基地运送了 $j$ 吨水果，基地一使用了 $j$ 个机器，基地二使用了 $l$ 个基地，的最小答案。$0$ 表示最小运输时间，$1$ 表示最小加工时间。 考虑转移。对于一个新的果园，我们枚举 $p$ 表示为它对第一个基地运送的货物。当 $p=0$ 时，基地一需要使用 $c_{1,i}$ 的机器；当 $p=a_{i}$ 时，基地二需要使用 $c_{2,i}$ 的机器。当新的运输时间或新的最小加工时间更优的话，就要对 dp 数组进行状态转移。 $ \begin{cases} dp_{i,j,k,l,0}=\min\left\{dp_{i,j,k,l,0},\max\left[dp_{i-1,p,r1,r2,0},d_{1,i}\times j,d_{2,i}\times(a_i-j)\right]\right\} \\ dp_{i,j,k,l,1}=\min\left\{dp_{i,j,k,l,0},\max\left[dp_{i-1,p,r1,r2,1},u_{1,i}\times j,u_{2,i}\times(a_i-j)\right]\right\} \end{cases} $ 然后不知道那里写错了，挂 $60$ 分。 ## 最佳位置 有 $n$ 个座位，会有 $m$ 个人按照顺序进来。令 $f_i$ 表示为离 $i$ 最近的被占用的座位 $j$ 离 $i$ 的距离。新来的人会选择最小 $f_i$ 的 $i$，如果有多个选择最小的 $i$，在 $i$ 位置上落座。有的人会在中途离开，空出位置。你需要输出每个人落座时会选择什么位置。 --- 采用暴力。对于每个位置 $i$，我们使用数组 $f_i$ 表示位置 $i$ 是否被占用，这样我们就可以解析出每个询问是加入还是退出了。对于加入询问，我们使用数组 $a$，令 $a_i$ 表示为位置 $i$ 离它最近的已被占用的位置 $j$ 的距离（$|i-j|$），然后遍历数组 $a$，找到最大的 $a_i$ 且 $i$ 较小，将该位置设为已被占用。 对于删除询问，我们加入数组 $s_i$ 表示为编号为 $i$ 的人坐到的位置，那么只需要将 $s_i$ 的位置设为 $0$（${} f_{s_i}\gets 0 {}$）即可。需要注意的是，在每次询问过后，都要重新更新 $a$ 数组。时间复杂度 $\mathcal O(mn^2)$。 ## 跑步路线 有 $n$ 点 $m$ 边的连通图，第 $i$ 条边连接 $(u_i,v_i)$，花费时间为 $w_i$。规定长度为 $k$ 的路径 $a$，要按照顺序一个个经过结点 $a_i$（$a_i$ 可能重复）。经过的路线必须在图的最小生成树上，且除了起始结点与终点结点外，每个经过的结点都要额外增加 $t_0$ 的时间。问你最短时间的合法路线的时间是多少。、 --- 首先，本题在题面已经告诉我们每条边的边权互不相等，那么最小生成树就是唯一的。我们将所有的边收集起来，跑 Kruskal 算法求出最小生成树并保存，即可干掉「路径在最小生成树上」这个条件。 接下来我们考虑 $a_{i-1}$ 到 $a_i$ 的最短路径。由于最小生成树是一棵树，那么其树上任意两点都只有一条最短路径，而且会经过它们的最近公共祖先（LCA）。 因此我们要求最近公共路线，采用倍增方式。令 $dp_{i,j}$ 表示为结点 $i$ 往上 $2^j$ 个父亲，那么不难推出 $dp_{i,j}=dp_{(dp_{i,j-1},j-1)}$。在求 $(x,y)$ 的 LCA 时，我们首先要让 $d_x=d_y$（$d_i$ 表示为 $i$ 的深度）。如果此时 $x=y$，那么 $x$ 或 $y$ 就是它们的最近公共祖先。否则遍历 $i\ge 1$，如果 $dp_{x,i}\ne dp_{y,i}$，那么就让 $x\gets dp_{x,i},y\gets dp_{y,i}$。 最后考虑求最短距离。本题当中有点权 $=t_0$，但是我们可以将点权包含在边权里面，最后减去 $t_0$。令 $p_i$ 表示为 $1\rightarrow i$ 的路径经过的边权，那么 $x\rightarrow y$ 的最小距离便是 $p_x+p_y-2\times p_l$，其中 $l$ 是 $(x,y)$ 的最近公共祖先。 时间复杂度 $\mathcal O(m\log_2 m+(n+k)\log_2 n)$，不知道哪里写错了 TLE ${} 5$ 分。 ## 总结 - **排名**：$18$； - **比赛分数**：$190/400$； - **情况**：相比 [[2024.10.2 模拟赛]]，《考得非常不错》； - **问题**：细节把控非常《到位》。