ACGO 第 12 次排位赛题解
写在前面
本场比赛所有题目经过一轮 ChatGPT−4o\tt{ChatGPT-4o}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」生成的变量；
每个变量名为一个字符串，一共有 NNN 个变量名，我们可以使用一个执行 NNN 次的循环，每次循环，使用一个 std::string 类型变量 s 读入变量名，并使用 s.size() 来获取字符串的长度，若长度大于 555 则令 m 加 111。
最终就可以得到 NNN 个变量名中「AI」编写的变量的数量 M。
由于需要向上取整，我们可以使用以下方法……
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 统计区间内奇数与偶数的数量
标签：前缀和；数学
对于每个查询，若直接使用循环暴力统计 [Li,Ri][L_i, R_i][Li ,Ri ] 内的奇数或偶数，时间复杂度为 O(Ri−Li)\mathrm{O}(R_i - L_i)O(Ri −Li )。本题 1≤Li≤Ri≤1091 \le L_i \le R_i \le 10^91≤Li ≤Ri ≤109。暴力统计会超出时间限制。
我们不妨思考一个问题：给定任意正整数 NNN，求 [1,N][1, N][1,N] 中所有「奇数」的数量，如何解决这个问题？
不妨枚举，打表找找规律，1,3,5,7,9,11,⋯1, 3, 5, 7, 9, 11, \cdots1,3,5,7,9,11,⋯。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 火星背包 II
标签：背包问题
本道题目不难想到套用经典的「01背包问题」，定义 dp[i][j]\tt{dp[i][j]}dp[i][j] 为前 iii 个物品，背包容量为 jjj 可以获取的最大价值，然后使用 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])}dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]) 进行转移。
此种做法只能够拿到一部分分数（约 40%40\%40%），无法通过本题，原因是本题背包的容量和物品的重量都特别大 (1≤wi≤M≤109)(1 \le w_i \le M \le 10^9)(1≤wi ≤M≤109)。使用上述方式解决这道题目的时间复杂度为 O(NM)\mathrm{O}(NM)O(NM)。
但本题 NNN 以及 viv_ivi 的值都比较小，我们不妨……
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 可分数列
标签：构造；数学
对于本道题目，不难发现，公差以及首项的值是不重要的，我们需要关注的点主要是如何将这 4N+24N + 24N+2 个元素去掉 222 个元素以后按照题目要求的形式分成 NNN 组。
首先观察样例。
我们将按照『从上到下』，『从左到右』的顺序，除最后一列外，每列 NNN 个元素的方式排列。
将 A2A_2A2 和 A13A_{13}A13 去除掉后，可以将剩余的元素分成 [1,4,7,10][1, 4, 7, 10][1,4,7,10]，[5,8,11,14][5, 8, 11, 14][5,8,11,14]，[3,6,9,12][3, 6, 9, 12][3,6,9,12] 三组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 花火大会
标签：最短路径；广度优先搜索
本题若只有一处放烟花的地方，那么则为「单源无权最短路问题」。
当有多处放烟花的地方且放烟花的时间相同，则为「多源无权最短路问题」。
以上两个问题都可以使用 BFSBFSBFS 解决。但本题需要解决的是一个「多源不同权的无权最短路问题」。
容易想到的一个策略是使用「优先队列」替换「队列」来实现 BFSBFSBFS。但此种方法的复杂度为 O(NMlogNM)\mathrm{O}(NM\log{NM})O(NMlogNM) 在本题时间复杂度比较大的情况下无法通过本题。
假设队列中的点是按照最短路的大小从小到大排好序的，例如：
[1,2,2,2,3,3,3,4,5][1, 2, 2, 2, 3, 3, 3, 4, 5][1,2,2,2,3,3,3,4,5]
第一个点的最短路为 111，当其出队的时候，扩展的到的点的最短路为 222。
我们需要将其放在一个合适的位置，使得每个点第一次出队的时候，一定是未确定最短路的点中，最短路最小的点（DijkstraDijkstraDijkstra 算法的思想）。
那么我们不妨将这些点按照最短路大小进行分组：
[[1],[2,2,2],[3,3,3],[4],[5]][[1], [2, 2, 2], [3, 3, 3], [4], [5]][[1],[2,2,2],[3,3,3],[4],[5]]
我们只要能够从小到大依次遍历这些组，并将扩展出的点放入对应的「组」中即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 剑之试炼
标签：最短路径；状态压缩动态规划；广度优先搜索；
本道题目包含多个子问题，如果不加以梳理，会非常复杂，并且在梳理完毕后依然编写大量代码，并且需要特别注意实现细节，非常考验「力量」（毅力）,「智慧」与「勇气」。
由于要求必须击败所有的「波克布林」，且从地下 iii 层传送至地下 i+1i + 1i+1 层须花费 111 秒的时间，所以我们可以把击败波克布林需要的时间和传送的时间预处理，后面就可以把所有的「波克布林」当成同一种去处理；把此部分花费的时间记为 cost\tt{cost}cost。
把所有的波克布林当成「特殊点」，并将其在地图中标记为 *，接下来都可以把问题转化成：访问 KKK 层地图上的所有特殊点需要最短时间，将其标记为 mint\tt{mint}mint。
那么本题的答案为 cost+mint\tt{cost + mint}cost+mint。
接下来解决如何计算 mint\tt{mint}mint 的问题。
因为计算 mint\tt{mint}mint 比较复杂，我们可以将其划分成若干个子问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
