1 条题解
-
0
题目分析
A. 自动化生产
将 , , 连着三天记为一轮,先算出总共走的完整轮数 ,最后再算剩下的路程 % 需要走的天数 ,最后答案为 。
B. 书架平衡
可以发现 满足单调性( 越大花费越少),我们可以二分 ,然后 检查是不是符合条件。
检查实现:
- 对于每一个位置 ,需要进行的消除次数是 。
- 为了满足 的条件, 可行的范围是 。
- $\min u_i = \max(0, u_i - (u_i + d_i - h)) = \max (0, h - d_i)$ , 。
时间复杂度: 。
C. 特工潜行
对于每一轮操作,我们用数组维护若干个 ,表示在当前轮操作完后,“夜影”特工可能到达的位置。初始化这个数组为 。
对于每一次操作,遍历每一对 进行更新
- 如果 ,那么操作后可能的区间为 。
- 如果 ,那么操作后可能的区间为 。
- 如果 ,那么操作后可能的区间为 , ,当 时,还有区间 。
操作完排序统计个数即可。排完序后可以对于有交叉的 进行合并,减少后续操作的次数。
乍看之下,该解法的时间复杂度似乎是 ,因为可能存在的区间数量会达到 级别,且每个区间都需要更新。但通过观察可以发现,实际同时存在的有效区间不会超过 个:初始区间 (可向左右扩展)、最左端点 (仅能向右扩展)以及最右端点 (仅能向左扩展)。
时间复杂度: ,维护的区间数量为常数级别。
D. 果园争锋
对于果农 ,最优的操作是在剩余字符串还有 的时候,选 ,否则选 。所以当两个果农刚好能一人选一次到游戏结束时,子串中一定满足 。
- 当 时,果农 能在两人一人选一次后多选一次,玩家一获胜。
- 当 时,
- 当 时,在倒数第二轮选完之后,刚好只剩下两个 、一个 。果农 获胜。
- 剩余其他情况下,带倒数第二轮选完之后会剩下两个 和若干个 ,果农 获胜。
果农 获胜的数量就是所有满足的 或 的子串数量。
设 表示前 位的 的数量,所有以第 位结尾的子串中,果农 获胜的数量为满足 且 或 的 的数量(满足 或 ,其中 表示的是 的子串中的 数量。
最后只需要统计出满足 且 或 的 的数量即可。
时间复杂度: 。
本题考察了 DP,组合数学的相关知识。
30pts
我们用计数 。
设 表示前 个数,最后一个数是 的合法方案数,转移:。
+30pts
考虑 ,,假设 ,问题相当于求解值域 的不增序列,可以直接利用组合数插板法分析出答案。
80pts
上面两档分启发我们同时从 DP 和组合的角度考虑问题。
用每个 做分界点,把所有的数分组。
设离散化的数组为 ,则第 组的数包括 。
这样我们可以愉快地 了,设 表示前 个数,最后一个数在第 组的合法方案数。通过枚举 ,表示 全在第 组,进行转移:
$$dp_{i,j} = \sum_{k=1}^{i-1} \sum_{p>j} dp_{k,p} \times \binom{len + i - k - 1}{len - 1}$$100pts
这个内层求和显然可以用前缀和优化,所以总时间复杂度为 。
- 1
信息
- ID
- 197
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者