ACGO 排位赛#12 - 题目解析
本文同步于 CSDN：点击跳转
> 别问为什么没有挑战赛#11，因为挑战赛#11被贪心的 Yuilice 吃掉了（不是）。
>
> 本次挑战赛难度相比较前面几次有所提升。
>
> 爆料：小鱼现在已经入职了研发部门，排位赛的算分级制将在未来的几场排位赛中做出重大改变。之后就不会出现大家段位都很低的情况了。对于程度好的同学，稍微打一两把排位赛段位就会有很大的提升。
第一题 - 50%𝐴𝐼, 50%𝐻𝑢𝑚𝑎𝑛
题目链接跳转：点击跳转
STL 大法真好，用自带的 string.size() 方法就可以快速求出一个字符串的长度。具体思路见代码，根据题目要求模拟就好了。
本题的 AC 代码如下：
第二题 - 统计区间内奇数与偶数的数量
题目链接跳转：点击跳转
对于这种区间的问题，可以先考虑一部分。如果要求出从 [1,L][1, L][1,L] 区间内满足条件的数字我们应该怎么办？假设 LLL 是一个偶数，那么 [1,L][1, L][1,L] 区间的奇数和偶数就应该是 L/2L / 2L/2。相同地，假设 LLL 是一个奇数，那么 [1,L][1, L][1,L] 区间的奇数和偶数就分别是 L/2+1L / 2 + 1L/2+1 和 L/2L / 2L/2。注意到 L/2+1L / 2 + 1L/2+1 和 L/2L / 2L/2 两个公式都可以被简写成 (L+1)/2(L + 1) / 2(L+1)/2。
设 odd(L)odd(L)odd(L) 和 even(L)even(L)even(L) 分别为区间 [1,L][1, L][1,L] 的奇数个数和偶数个数。那么可以得出结论，如果要求 [L,R][L, R][L,R] 区间的奇数个数，答案就应该是 odd(R)−odd(L−1)odd(R) - odd(L-1)odd(R)−odd(L−1) 和 even(R)−even(L−1)even(R) - even(L-1)even(R)−even(L−1)。
本题的 AC 代码如下，代码并没有使用函数，见谅：
第三题 - 火星背包 II
题目链接跳转：点击跳转
一道反向 0/10/10/1 背包的模板题目。通常，0/10/10/1 背包问题的目标是选择若干物品，使得这些物品的总重量不超过背包容量，并且这些物品的总价值最大化。而反向 0/10/10/1 背包问题则是反其道而行之，其目标是选择若干物品，使得这些物品的总重量不低于给定的最小值，并且这些物品的总价值最小化。
主要就是状态的定义比较难：设 dp[j]dp[j]dp[j] 表示恰好凑出总重量为 jjj 的最小代价。那么我们可以得到如下的状态转移方程：
dpj=min(dpj,dpj−wi+vi);dp_j = \min(dp_j, dp_{j-w_i} + v_i); dpj =min(dpj ,dpj−wi +vi );
根据状态的定义，我们将 dpdpdp 数组一开始全部初始化为正无穷大，同时另 dp0=0dp_0 = 0dp0 =0，表示恰好凑出重量为 000 的物品的最小代价为 000，正无穷大代表暂时还没有答案，需要在后续的循环中更新。
之后就是跑一遍正常的 Knapsack 01 代码就好了。在输出答案的时候，我们需要找到一个满足条件 (dp[i]≤m)(dp[i] \le m)(dp[i]≤m) 的最大值。用一个 for 循环就可以搞定了。
本题的 AC 代码如下：
第四题 - 可分数列
题目链接跳转：点击跳转
题目很简单，但需要仔细想一会儿才行。这道题的解决思路就是 找规律！没错，就是找一下规律就好了。我们只需要关注如何将这 4N+24N + 24N+2 个数列在去掉两个元素后可以被平均分成 NNN 个等差数列。
通过手动模拟的方式，注意到我们只需要把这些数字竖着排列就可以解决问题。另每一列有四个元素，但其中有两列有五个元素（代表 4N+24N + 24N+2 的 +2+2+2 部分），共有 NNN 列。例如数列 [1,3,5,7,9,11,13,15,17,19,21,23,25,27][1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27][1,3,5,7,9,11,13,15,17,19,21,23,25,27]。竖着排列之后就是这个样子的：
可以看到这些元素构成了三个等差数列，且两个等差数列的长度为 555。那么对于长度为 444 的等差数列我们完全可以不用管，直接输出就好了。而对于这两个长度为 555 的等差数列，我们考虑从这两个等差数列中各删除一个数字来构成新的等差数列。综合来看，我们发现删除元素 333 和 252525 后，新的两个等差数列依旧满足题目限定的条件。
再多列举几个例子，发现规律也是相通的。那么因此我们可以得出结论，对于任意一个长度为 4N+24N + 24N+2 的等差数列，只需要删除这个等差数列的第 222 项和第 4N+14N + 14N+1 项，剩下的 4N4N4N 个元素一定可以组成 NNN 个长度为 444 的等差数列。
> 关于本题的更多信息，可以阅读 アイドル 老师的题解作为补充：链接跳转。
找到规律后代码就很好写了，本题的 AC 代码如下：
第五题 - 花火大会
题目链接跳转：点击跳转
> 这道题的输出不是故意为难大家，因为输出实在太大了，超出了 CF 限定了 64MB 的限制，因此只能将输出地图改为了输出地图的哈希值（对于没有学过哈希的同学来说，输出答案也是一个比较困难的事情）。
本道题的难度其实不大，就是一个多源不同权的无权最短路问题。但由于数据量比较大，使用普通的优先队列维护会超时（别问我是怎么知道的，我一开始就用了优先队列，然后在 #13 测试点就 TLE 了），因此我们需要考虑如何找到一个 workaround 来替换优先队列。
注意到我们只需要另外再使用一个 while，在每次获取头节点的时候判断某一个烟花是否刚好在该时间点燃放，如果烟花正好燃放，我们就把这个烟花的坐标加入到队列之中。
由于每一个烟花每一个单位时间只会影响附近的一个格子，说明在放入烟花的时候队列中队头和队尾的权重是相同的，这样就保证队列内的元素权重一定是单调递增的。这这种情况下，这道题就转换成了使用 BFS 来求多源无权最短路的条件。
本题的 AC 代码如下：
第六题 - 剑之试炼
题目链接跳转：点击跳转
> 这道题超级恶心，我发自内心地对那些在比赛过程中 AC 此题目的同学表示尊敬。
思路上非常好想，由于所有的怪兽都要打，且打每一个怪兽的时间都是固定的，因此我们可以在一开始就先预处理出打完所有怪兽的时间，需要优化的就只有赶路的时间了。
先考虑每一层的情况，对于任意一层来说，关键点就是找到一个最优的路径（从某一个起点出发，经过所有的点后再传送到下一层的最短路径）即可。学习过状态压缩动态规划的同学可以很容易想到模板题【最短 Hamilton 路径】（洛谷链接：链接跳转）。
对于每一层来说，具体的实现方法和函数如下：
1. cover(dist, grid, "#*");
* 将dist和grid中标记为"#"或"*"的所有障碍物进行覆盖处理。这一步的作用是标记出所有不可通行的区域，为后续的距离计算或路径规划提供基础。
2. getMinDist(dist, grid, "#");
* 计算从当前所在位置到grid中标记为"#"（障碍物）位置的最短距离。这一步的作用是为后续的路径规划获取到障碍物的距离信息，方便下一步进行路径选择。
3. hamilton(dist, grid);
* 在dist和grid上执行哈密顿路径（Hamiltonian Path）的计算，目的是找到一条经过所有目标点的路径。这一步的作用是根据前面的距离信息，找到一条经过所有必经点的路径。
4. cover(dist, grid, "#.");
* 对dist和grid中标记为"#"（障碍物）和"."（空地）的部分进行覆盖处理。这一步是为了确保后续的距离计算排除已标记的障碍物，并识别可通行的路径。
5. getMinDist(dist, grid, "#");
* 再次计算从当前所在位置到grid中标记为"#"的最短距离。这一步是为了更新经过路径覆盖处理后的最短距离，确保得到最新的距离信息。
除此之外就是一些小的细节优化了，具体请参阅代码注释。
本题的 AC 代码如下（本代码参考了黄老师的 std，并加以修改（我是不会说我数组传来传去把自己传死了，讨厌指针的一天）），若需要更详细的解答，可以 参考本文：
