【题解】2021牛客OI赛前集训营-提高组（第六场）

提高组题解

A 旋律的总数

最少部分的分数可以通过笔算获得。

$40\%$ 的分数可以暴力枚举所有可能性后去重得到，时间复杂度 $O(2^{nm}*n)$ 。

注意到对于现有合法序列 $(a_1, a_2, \cdots, a_n)$ ，重复的序列只有 $m$ 种，即 $k\in [1,m], ((a_1 + k) \% m, (a_2+k) \%m ,\cdots)$ 。由此，我们可以通过动态规划来维护，用 $d[i]$ 表示长度为 $i$ 的不重复序列的个数，显然有转移方程 $d[i] = d[i-1] * m$ ，初始值 $d[0]=1, d[1]=1$ 。

我们发现，上式 $d[n] = m^{n-1}$ 。可以直接用快速幂计算，时间复杂度 $O(m\log n)$ 。相当于只要强制使第一个选 $1$ ，之后就不会重复。

另一种思路是：所有的序列个数是 $m^n$ 个，注意到每个序列会重复 $m$ 次，答案即 $m^n / m = m^{n-1}$ 。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022069

B 水果加工

对于1~4组数据，暴力枚举每个果园里水果送去哪个基地即可。

对于5~8组数据，考虑到运输时间为0，则可以用 $b^2$ 的背包来直接求解加工时间，时间复杂度 $O(b^2\sum a_{i})$ 。

对于9~12组数据，考虑运输时间，可以发现最多只有 $\sum a_{i}$ 种情况，枚举每种运输时间 $T_{d}$ ，则可以对加工过程再加一层限制，即对于每一种分配方案，其运输时间须小于 $T_{d}$ 。又由于 $c_{ij}=1$ 且 $b_{i}=40$ ，则在满足运输时间限制的前提下，将第 $i$ 种水果送往加工时间少的工厂加工即可。

对于13~20组数据，枚举可能的运输时间 $T_{d}$ ,在运输时间 $T_{d}$ 的限制下进行背包即可，复杂度 $O(b^2(\sum a_{i})^2)$

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022067

C 最佳位置

可以把每部分连续的空座位视为一个二元组 <起始位置，连续空座位长度>。

注意到每次新来的人会选择连续空座位长度最大的，如果有多个，会选择起始位置最小的，然后坐在中间。（除了坐位置 1 和位置 n 的，需要特判）

为了方便描述问题，我们将连续的空座位段简称为空段。因为座位从左往右分别编号从 $1$ 到 $n$ ，后文的描述也会用左右来替代数字大小。

我们不妨仔细分析下问题，把问题简化为进入和离开两个部分：

进入部分，注意到进入的人除了选择最左边或者最右边，会选择空段中，连续长度最长的。如果有多个最长的，会选择编号最小的。不如特判最左最右的情况，来集中讨论选择非最左最右的情况：如果选择的是非最左最右，进来的人一定会选择坐在中间，如果空段长度为偶数，则会坐在中间靠左（编号较小）的位置。选择后，因为坐在中间，会把这个空段分为两部分。我们会猜测，可能需要一个可以快速维护最长空段的数据结构。
离开部分，注意到离开的人可能是任意的情况，同样，最左边和最右边的情况比较复杂，考虑特判。对于从中间离开的人，如果坐在位置 $k$ ，根据位置 $k-1$ , $k+1$ 是否有人，可以分为三种情况：

2.1. $k-1$ 和 $k+1$ 都没有人：仅增加一个长度为 $1$ 的空段。

2.2. $k-1$ 有人或 $k+1$ 有人：和一侧的空段合并，调整其起始且长度加一。

2.3. $k-1$ 和 $k+1$ 都有人：将两侧的空段合并成一段，起始各取最小和最大，长度加一。

而合并空段可以简化为空段的删除和插入。我们如果能将空段以编号顺序维护，就可以轻松地维护空段。

经过综上的讨论，我们发现需要一个能根据两种排序手段维护空段的数据结构。一个便捷的想法是维护两个 set ，一个 set 按照最长排序，如果有多个等长空段按编号排序，称为 A ；另一个 set 按照编号排序，称为 B 。进入部分直接查询 A ，离开部分查询 B。因为两者都是在维护空段，只要能查询到空段的完整信息就可以。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022064

对于开头和结尾怎么特判，就依赖于具体的代码实现，可以参考标程。

D 跑步路线

首先因为边各不相同，所以最小生成树唯一，问题可以转化成在树上的求 $k$ 次距离的问题。

最简便的可以是暴力求距离，暴力dfs，视水平可以获得30~60分。

进阶一点的做法是，可以任选一点为根，求有根树上两点 $u,v$ 的距离就等于求 $u-> LCA(u,v) -> v$ 的距离，LCA表示最近公共祖先。如果设 $dist(x)$ 表示从根到 $x$ 点的距离，那么 $u,v$ 之间的距离就等价于 $dist(u) + dist(v) - 2* dist(LCA(u,v))$ 。