竞赛讨论区 > 【题解】2021牛客OI赛前集训营-提高组(第六场)
头像
Trote
编辑于 2021-10-18 23:20
+ 关注

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

提高组题解

A 旋律的总数

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

的分数可以暴力枚举所有可能性后去重得到,时间复杂度

注意到对于现有合法序列 ,重复的序列只有 种,即 。由此,我们可以通过动态规划来维护,用表示长度为的不重复序列的个数,显然有转移方程,初始值

我们发现,上式。可以直接用快速幂计算,时间复杂度。相当于只要强制使第一个选,之后就不会重复。

另一种思路是:所有的序列个数是个,注意到每个序列会重复次,答案即

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

B 水果加工

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

对于5~8组数据,考虑到运输时间为0,则可以用的背包来直接求解加工时间,时间复杂度

对于9~12组数据,考虑运输时间,可以发现最多只有种情况,枚举每种运输时间,则可以对加工过程再加一层限制,即对于每一种分配方案,其运输时间须小于。又由于,则在满足运输时间限制的前提下,将第种水果送往加工时间少的工厂加工即可。

对于13~20组数据,枚举可能的运输时间,在运输时间的限制下进行背包即可,复杂度

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

C 最佳位置

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

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

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

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

  1. 进入部分,注意到进入的人除了选择最左边或者最右边,会选择空段中,连续长度最长的。如果有多个最长的,会选择编号最小的。不如特判最左最右的情况,来集中讨论选择非最左最右的情况:如果选择的是非最左最右,进来的人一定会选择坐在中间,如果空段长度为偶数,则会坐在中间靠左(编号较小)的位置。选择后,因为坐在中间,会把这个空段分为两部分。 我们会猜测,可能需要一个可以快速维护最长空段的数据结构。

  2. 离开部分,注意到离开的人可能是任意的情况,同样,最左边和最右边的情况比较复杂,考虑特判。对于从中间离开的人,如果坐在位置 ,根据位置 , 是否有人,可以分为三种情况:

2.1. 都没有人:仅增加一个长度为 空段

2.2. 有人或 有人:和一侧的空段合并,调整其起始且长度加一。

2.3. 都有人:将两侧的空段合并成一段,起始各取最小和最大,长度加一。

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

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

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

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

D 跑步路线

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

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

进阶一点的做法是,可以任选一点为根,求有根树上两点的距离就等于求 的距离,LCA表示最近公共祖先。如果设 表示从根到 点的距离,那么 之间的距离就等价于

通过这种方法直接暴力向上走可以降低暴力范围,而取得更多的分数。

LCA 是一个经典问题,类似于RMQ(区间最小值),有很多预处理后 的求法。比如倍增、RMQ等。

时间复杂度

注意到数据范围似乎稍稍超出了 long long ,故如果是使用 long long 范围做的可能会丢掉分。

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

全部评论

(9) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐