蓝桥杯2025省赛A组游记题解

前言

说起来这届蓝桥杯参赛过程还挺波折的。原定的时间恰好碰到北京大风（一直呆在室内，没有体验一下大风有多大）推迟后的时间又和你航的数分期中撞了……

一个周末内前后脚比赛和考试，怎么想都很痛苦吧。此外这周内还塞满了许多琐事，导致根本没有大块的空闲时间进行复习。直到周五晚上十点多排练结束回到寝室才想起来第二天就要比赛了，把一些基础的数据结构和算法过了一遍，心里稍微有了点底。

众所周知，备用卷总是容易出现难度或区分度方面的问题。这届也是如此，总体上难度偏低，区分度也不足。

不同于2024年A组真题E/F/G/H有层次的难度设计与全面的知识面考察，这套题在G题之前几乎没有给到任何强度。而G题又是一个显而易见的线段树模板题，于是区分度等于是全部由H题的差分约束提供了（很不幸我被区分了）

在此写一篇个人向题解，赛时心路历程会穿插其中。

A

题目大意： 大盒尺寸 \(200\times 250\times 240\)，小盒尺寸 \(30\times 40\times 50\)，问大盒里能放几个小盒。

标签： 小学数学

我认为将小学二年级数学题放在大学生竞赛里是不妥的。所以我认真思考了很久哪里有坑。

但事实上这就是一道小学二年级数学题，无语了家人们。

注意到有 \(30|240\)，\(40|200\)，\(50|250\) ，所以答案就是大体积除以小体积。

哎哎，出题人的苦心。

B

题目大意： 求符合要求的正整数 \(n\) 的数量：\(n+20255202\) 和 \(n+10244201\) 都是完全平方数。

标签： 枚举/初中数学

赛时我先考虑了直接枚举 \(n\)。分别设 \(a^2=n+20255202\)，\(b^2=n+10244201\)。由于 \(a^2>b^2\)，因此也有 \(a^2\geq (b+1)^2\) ，稍加变形可得：\(b\leq\frac{a^2-b^2-1}{2}\) ，其中 \(a^2-b^2\) 是定值 \(10011001\) 。那么 \(b\) 的枚举范围就不超过 \(5005500\) ，在计算机的承受范围之内。枚举时判断 \(b^2+10011001\) 是不是完全平方数即可。

不过我最终选择的并非此解法。注意到 \((a+b)(a-b)=10011001\) ，可以考虑对 \(10011001\) 进行因数分解。由于这是个奇数，所以因数一定同为奇数，解出来的 \(a\) 和 \(b\) 一定是整数。去掉那些 \(a^2\leq20255202\) 的情形后，\(10011001\) 剩下的因数对的数量便是最终答案。

比较幽默的是，我枚举因数的时候是从 \(2\) 开始的，因此最终答案少了一种，痛失五分。

C

题目大意： 用循环的字符串填充矩阵的每一行。每一行的字符串是 LANQIAO 循环左移对应次数后形成的串。求矩阵上 A 的个数。

标签： 模拟

既然数据范围这么小的话，先把矩阵填满，再取数 A 的数量就行了。没什么好讲的。

D

题目大意： 给定AB串，重复执行操作，每次删去一个AB子列直至不能操作。问串最终长度可能的最大值。

标签： 贪心，双指针

显然串最终形态一定形如 BB...BBAAA...A，否则就还能继续操作。我们应尽量删去所有靠左的A，所有靠右的B。

那么贪心地去做，用一个双指针维护这个过程。每次删去串中第一个 A 和最后一个 B 。直到双指针相遇。

贪心的正确性是显然的。因为靠左的 B 与靠右的 B 相比，不被删去从而留在最终串中对答案做出贡献的机会更大。

E

题目大意： 给定一棵树，每次出发走至多 \(k\) 步，步长为 \(1\) 或 \(2\) ，然后获得路径终点的权值。你可以从 \(1\) 号节点出发无数次。问最终获得的权值。

标签： 树的遍历

注意到 \(2k\) 以内的所有数字都可以写成不超过 \(k\) 个 \(1\) 或 \(2\) 的和，我们求出所有深度不大于 \(2k\) 节点的权值和即可。（初读题的时候还以为只能出发一次，以为是个树形DP类似物，但实际上……）

F

题目大意： 给定 01 串，问有多少对不重叠的子串互为反串（每个对应位置均相反）

标签： 计数

不太记得思路从何而来了，这里直接给出我的做法吧：

记所给 01 串 \(s\) 的长度为 \(n\) 。

枚举两串首间的距离 \(j\) ，记 \(t_i=s_i+s_{i+j}\) \((i+j\leq n)\) ，那么 \(t_i=1\) 说明： \(s_i\) 与 \(s_{i+j}\) 相反，\(s_i\) 可成为前串的一部分。

如果 \(t_{L...R}\) 都等于 \(1\) ，那么我们从这些能成为前串一部分的字符中任取一段 \(s_{l...r}\left(L\leq l \leq r\leq R\right)\) ，都会有 \(s_i=1-s_{i+j}\left(l\leq i\leq r\right)\) 恒成立。

也就是说：如果 \(t_{L...R}\) 与 \(t_{L+j...R+j}\) 没有重叠部分 \((R<L+j)\) ，这一段对答案的贡献就是段内的子串数。对于段内每个字符 \(s_i\)，以它开头的子串数就是 \(R-i+1\)，整段的贡献为 \(\sum_{i=1}^{R-L+1}i.\)

那如果有重叠部分怎么办呢？其实也不难想。不论起点的位置，长度大于 \(j\) 的子串一定和后串重叠，不大于 \(j\) 的一定合法。所以我们只需对上面的计算方式稍作调整，改为 \(\sum_{i=1}^{R-L+1}\min(i,j).\) 可以和上式合并。

计算所有 \(j\) 下贡献的和即可。

时间复杂度 \(O(n^2)\)，可以通过此题。

G

题目大意： 维护一个支持入栈、出栈、以及查询栈顶前若干数乘积操作的栈。

标签： 线段树

单点修改，区间乘积查询，线段树的暗示已经给得很明显了。

考虑到栈内的数不超过 \(Q\) 个，线段树的容量开到 \(4e5\) 级别已经足够。

入栈操作就是把栈当前容量加一处的数修改为目标数；出栈操作只需让记录栈当前容量的变量自减；查询操作只需调用线段树区间乘积查询函数即可。

为了让超过 \(2^{32}\) 的数输出为 OVERFLOW，我们可以修改区间合并的函数。对每个节点以 \(-1\) 值记录乘积超出 \(2^{32}\) 的情况。区间合并时分以下情况（按从上往下的优先级判断）：

• 左右子区间节点值有 \(0\)，则父区间节点值为 \(0\)。
• 左右子区间节点值有 \(-1\) ，则父区间节点值为 \(-1\)。
• 左右子区间节点值乘积大于等于 \(2^{32}\) ，则父区间节点值为 \(-1\)。
• 左右子区间节点值乘积小于 \(2^{32}\) ，则父区间节点值为左右子区间节点值乘积。

剩下就是线段树的常规写法了。算是一道很好调的DS题了。

H

题目大意： 给定序列 \(a\) 以及若干约束 \((l,r,p,q)\)，求解序列内最大最小差值的可能最小值。约束的意义是：

\[\min_{l\leq x\leq r}a_x - \max_{p\leq y\leq q}a_y\geq ans \]

标签： 差分约束

太久没写差分约束了，已经不会写了。等学会了回来补（