官方题解｜排位赛#12

userId_undefined

アイドル

倔强青铜

2024-09-18 10:56:45

发布于：浙江

176阅读
0回复
0点赞

ACGO 第 12 次排位赛题解

写在前面

本场比赛所有题目经过一轮 ChatGPT−4o\tt{ChatGPT-4o} 测试，测试结果如下：

题目 A B C D E F
分数 100 160 110 14 187 0
测试点通过比例 20/20 20/20 10/25 1/25 11/25 0/35

本场排位赛的所有题目的难度评级为：

题目编号 题目标题 难度
A. 50%AI, 50%Human 入门
B. 统计区间内奇数与偶数的数量 入门
C. 火星背包 II 普及-
D. 可分数列 普及/提高-
E. 花火大会 普及/提高-
F. 剑之试炼 提高+/省选-

非常感谢大家参加本场排位赛！

直播预告

直播时间：9月14日（周六）16:00 开始
直播地址：B站ACGO官方账号
直播内容：排位赛#12复盘

题解简述

以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。

A - 50%AI, 50%Human

我们可以以使用一个变量 M 来统计所有「AI」生成的变量；
每个变量名为一个字符串，一共有 NN 个变量名，我们可以使用一个执行 NN 次的循环，每次循环，使用一个 std::string 类型变量 s 读入变量名，并使用 s.size() 来获取字符串的长度，若长度大于 55 则令 m 加 11。
最终就可以得到 NN 个变量名中「AI」编写的变量的数量 M。
由于需要向上取整，我们可以使用以下方法……

B - 统计区间内奇数与偶数的数量

标签：前缀和；数学

对于每个查询，若直接使用循环暴力统计 [Li,Ri][L_i, R_i] 内的奇数或偶数，时间复杂度为 O(Ri−Li)\mathrm{O}(R_i - L_i)。本题 1≤Li≤Ri≤1091 \le L_i \le R_i \le 10^9。暴力统计会超出时间限制。

我们不妨思考一个问题：给定任意正整数 NN，求 [1,N][1, N] 中所有「奇数」的数量，如何解决这个问题？
不妨枚举，打表找找规律，1,3,5,7,9,11,⋯1, 3, 5, 7, 9, 11, \cdots。

C - 火星背包 II

标签：背包问题

本道题目不难想到套用经典的「01背包问题」，定义 dp[i][j]\tt{dp[i][j]} 为前 ii 个物品，背包容量为 jj 可以获取的最大价值，然后使用 dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i])\tt{dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])} 进行转移。
此种做法只能够拿到一部分分数（约 40%40\%），无法通过本题，原因是本题背包的容量和物品的重量都特别大 (1≤wi≤M≤109)(1 \le w_i \le M \le 10^9)。使用上述方式解决这道题目的时间复杂度为 O(NM)\mathrm{O}(NM)。

但本题 NN 以及 viv_i 的值都比较小，我们不妨……

D - 可分数列

标签：构造；数学

对于本道题目，不难发现，公差以及首项的值是不重要的，我们需要关注的点主要是如何将这 4N+24N + 2 个元素去掉 22 个元素以后按照题目要求的形式分成 NN 组。

首先观察样例。

我们将按照『从上到下』，『从左到右』的顺序，除最后一列外，每列 NN 个元素的方式排列。
将 A2A_2 和 A13A_{13} 去除掉后，可以将剩余的元素分成 [1,4,7,10][1, 4, 7, 10]，[5,8,11,14][5, 8, 11, 14]，[3,6,9,12][3, 6, 9, 12] 三组。

E - 花火大会

标签：最短路径；广度优先搜索

本题若只有一处放烟花的地方，那么则为「单源无权最短路问题」。
当有多处放烟花的地方且放烟花的时间相同，则为「多源无权最短路问题」。

以上两个问题都可以使用 BFSBFS 解决。但本题需要解决的是一个「多源不同权的无权最短路问题」。

容易想到的一个策略是使用「优先队列」替换「队列」来实现 BFSBFS。但此种方法的复杂度为 O(NMlog⁡NM)\mathrm{O}(NM\log{NM}) 在本题时间复杂度比较大的情况下无法通过本题。

假设队列中的点是按照最短路的大小从小到大排好序的，例如：

[1,2,2,2,3,3,3,4,5][1, 2, 2, 2, 3, 3, 3, 4, 5]

第一个点的最短路为 11，当其出队的时候，扩展的到的点的最短路为 22。
我们需要将其放在一个合适的位置，使得每个点第一次出队的时候，一定是未确定最短路的点中，最短路最小的点（DijkstraDijkstra 算法的思想）。

那么我们不妨将这些点按照最短路大小进行分组：

[[1],[2,2,2],[3,3,3],[4],[5]][[1], [2, 2, 2], [3, 3, 3], [4], [5]]

我们只要能够从小到大依次遍历这些组，并将扩展出的点放入对应的「组」中即可。

F - 剑之试炼

标签：最短路径；状态压缩动态规划；广度优先搜索；

本道题目包含多个子问题，如果不加以梳理，会非常复杂，并且在梳理完毕后依然编写大量代码，并且需要特别注意实现细节，非常考验「力量」（毅力）,「智慧」与「勇气」。

由于要求必须击败所有的「波克布林」，且从地下 ii 层传送至地下 i+1i + 1 层须花费 11 秒的时间，所以我们可以把击败波克布林需要的时间和传送的时间预处理，后面就可以把所有的「波克布林」当成同一种去处理；把此部分花费的时间记为 cost\tt{cost}。

把所有的波克布林当成「特殊点」，并将其在地图中标记为 *，接下来都可以把问题转化成：访问 KK 层地图上的所有特殊点需要最短时间，将其标记为 mint\tt{mint}。

那么本题的答案为 cost+mint\tt{cost + mint}。

接下来解决如何计算 mint\tt{mint} 的问题。

因为计算 mint\tt{mint} 比较复杂，我们可以将其划分成若干个子问题。

userId_undefined
去预览
0/2000

全部评论 4

热门讨论