10
巅峰赛38题解
本次题目的总体难度如下,各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 山间烤羊 普及/提高- T2 山间营地音乐会 普及/提高- T3 山间抹茶宴 普及/提高- T4 山间双人探险 普及/提高- T5 深山能源网络 普及+/提高 T6 山中补给站 普及+/提高
T1 山间烤羊
题意简述
初始美味值为 000,每次炭烤增加 111(无使用次数限制),另有三种香料 a,b,ca,b,ca,b,c,每种最多使用一次,使用香料增加对应香气值且不耗时。求达到美味值 kkk 所需的最少炭烤分钟数。
解题思路
因为炭烤每分钟增加 111,所以最少炭烤时间等价于选择若干种香料(共 23=82^3=823=8 种组合),使香料总和不大于 kkk,且 kkk 减去香料总和最小。枚举所有香料组合,计算 k−sumk - sumk−sum 的最小值即为答案。
参考代码
T2 山间营地音乐会
题意简述
乐队需要五个位置:主唱、贝斯、鼓、吉他、键盘。现有 aaa 个主唱候选人,bbb 个贝斯候选人,ccc 个鼓手候选人,*** 个吉他手候选人,eee 个键盘手候选人。每个位置选一个人,同一个人不能兼两个位置,求不同乐队方案数。
解题思路
主唱、贝斯、鼓手的选择相互独立,分别为 a,b,ca,b,ca,b,c 种。对于吉他手和键盘手,从 d+ed+ed+e 人中选出 222 人,但其中两人都选键盘手的方案无效(因为键盘只有一个位置),所以有效方案数为从 d+ed+ed+e 人中选 222 人减去从 eee 人中选 222 人,即 (d+e2)−(e2)\binom{d+e}{2} - \binom{e}{2}(2d+e )−(2e )。答案即为 a×b×c×((d+e2)−(e2))a \times b \times c \times (\binom{d+e}{2} - \binom{e}{2})a×b×c×((2d+e
)−(2e ))。
参考代码
T3 山间抹茶宴
题意简述
有 nnn 个甜品,每个有抹茶浓度 aia_iai 和冰度 bib_ibi 。选择一个连续区间,要求区间内每个甜品的 ai+bia_i + b_iai +bi 都相等。区间美味值定义为 ∑i=lrai×(r−l+1)\sum_{i=l}^r a_i \times (r-l+1)∑i=lr ai ×(r−l+1),即区间内 aia_iai 之和乘以区间长度。求所有满足条件的区间中的最大美味值。
解题思路
令 si=ai+bis_i = a_i + b_isi =ai +bi 。满足条件的区间必须是 sss 值相同的连续段。对于每个连续的相同 sss 值的段,我们需要计算该段内所有子区间的 (∑ai)×len(\sum a_i) \times len(∑ai )×len 的最大值。由于段内 sss 值相同,但 aia_iai 不同,最大美味值出现在整个段上,因为 aia_iai 均为正数,扩大区间会使 (∑ai)×len(\sum a_i) \times len(∑ai )×len 增大。因此对每个连续段,取整个段,计算段长 lenlenlen 与 aia_iai 前缀和之差乘积,取最大值。
参考代码
T4 山间双人探险
题意简述
有 n+1n+1n+1 个石台,编号 000 到 nnn。第 000 个石台为红色,是红叶的起点。每个石台最多踩一次。红叶只能跳到红色石台,墨岩只能跳到黑色石台。两人轮流跳跃,红叶先跳。若当前轮到的探险家无可用石台则结束。求能获得的最大总危险系数之和。
解题思路
由于跳跃顺序固定:红、黑、红、黑……,且可以跳到任意未被踩踏的对应颜色石台,最优策略是每次从当前颜色中选取危险系数最大的石台。将红色石台(不包括起点)和黑色石台分别排序,按从大到小交替取数,取到某颜色无剩余时停止。累加所有取到的值。
参考代码
T5 深山能源网络
题意简述
有 nnn 个节点和 mmm 个项目,每个项目可选择连接两个端点 aia_iai 或 bib_ibi 中的一个,获得能量 wiw_iwi 。每个节点最多参与一个项目,求最大总能量。
解题思路
将每个项目视为一条边 (ai,bi)(a_i, b_i)(ai ,bi ),权值为 wiw_iwi 。问题等价于在图中选择若干条边,使得每个节点的度数不超过 111,即选出一个边集构成一个匹配(但允许有环?注意每个节点最多选一条边,所以实际选出的边集形成若干个连通块,每个连通块要么是一棵树(边数 = 点数 - 1),要么是一个基环树(边数 = 点数)。由于项目可以在两个端点中任选一个,相当于每条边可以消耗一个端点,因此每个连通块内最多可以选的点数为节点数,但必须满足边数不超过节点数(否则无法分配)。按权值从大到小排序,用并查集维护连通块,记录每个块的点数和已选边数,若加入当前边不违反“边数 <
点数”的约束则选择该边并更新。
参考代码
T6 山中补给站
题意简述
有 nnn 种物资,每种价格 gig_igi 、体积为 111,可无限购买。求在总花费不超过 VVV 的前提下,恰好装满体积为 mmm 的背包的方案数,对 109+710^9+7109+7 取模。
解题思路
完全背包计数问题。设 dp[j][k]dp[j][k]dp[j][k] 表示花费为 jjj、已选 kkk 件物品的方案数。对每种物资 gig_igi ,枚举花费 jjj 从 gig_igi 到 VVV,枚举数量 kkk 从 111 到 mmm,进行完全背包转移:dp[j][k]+=dp[j−gi][k−1]dp[j][k] += dp[j-g_i][k-1]dp[j][k]+=dp[j−gi ][k−1]。最后累加所有花费 ≤V\le V≤V 且 k=mk=mk=m 的方案数。
参考代码
有帮助,赞一个