洛谷蓝桥杯省赛模拟赛 2026 文字版题解

· · 算法·理论

本题解不含代码。含代码的直播讲解需要购买，购买价格为 10 元。如果错过直播讲解也没关系，依然可以观看回放。

讲评链接：https://class.luogu.com.cn/course/LGR276 。

日期统计

注意到规定范围内的天数较小，因此考虑对于每个日期枚举计算其是否符合条件。

对于每一天，我们可以考虑将其转换为字符串之后对于每个数字统计其出现的个数，如果满足条件就将答案 +1。

最终得到答案为 210778。

编程比赛

令 A_1=789456，D_1=567890，T_1=901234，A_2=654321，D_2=876543，T_2=500001。

最直接的想法是枚举第一轮的所有比赛日期和第二轮的所有比赛日期，判断是否满足第一轮日期小于第二轮日期。但两轮比赛场数最多可达 10^6，总枚举量为 T_1 \times T_2，会花费大量时间，可以考虑优化。

注意到两轮比赛的日期都是等差数列，我们可以只枚举第一轮比赛的日期，然后快速计算第二轮比赛中有多少场比赛的日期严格大于当前枚举的第一轮日期。

设第一轮的一个比赛日期为 t，第二轮比赛日期序列为：

a_2, a_2 + d_2, a_2 + 2d_2, \dots, a_2 + (T_2-1)d_2

我们需要统计其中大于 t 的日期个数。

可以先计算第二轮中小于等于 t 的比赛场数，记为 x，那么大于 t 的场数就是 T_2 - x。

第二轮中小于等于 t 的比赛场数 x 满足：

因此：

x = \min\left( \max\left(0, \left\lfloor \frac{t - a_2}{d_2} \right\rfloor + 1\right), T_2 \right)

然后对第一轮的每个比赛日期 t，累加 T_2 - x 即可。最终得到答案为 192939070136。

跳柱文明

本题考察了题意的模拟，核心思路是遍历每个相邻的柱子对，检查它们之间的高度差是否满足条件。

对于每两个相邻的柱子，我们都计算后者高度减去前者高度，用 if 语句判断是否小于等于 1；计算前者高度减去后者高度，用 if 语句判断是否小于等于 x。

若所有相邻柱子对均满足条件，则小 Z 可以成功到达终点。

注意需要多测清空。时间复杂度：O(T\times N)。

合成西瓜

下文中的 n 为 x,y 的值域。

记 f_x 表示合成大小为 x 的西瓜需要的最少西瓜数。

直接做时间复杂度为 \mathcal O(Tn^2)，期望得分 30 分。使用前缀和优化后时间复杂度为 \mathcal O(Tn)，期望得分 70 分。

考虑优化，发现当 x\ge y+2 时，f_x=2f_{x-1},f_{y+1}=y+1。容易推出 f_x=2^{x-y-1}(y+1)。

时间复杂度 \mathcal O(T\log n)，期望得分 100 分。

采矿文明

首先可以想到固定选择的矿井中编号最大的那个，这样就能直接算好 C_i 的和了。

然后就考虑固定了编号最大的矿井后的最大开采量是多少，贪心的选择 A_i 前 K 大的那 K 个矿井（如果不足 K 个就全选），记这些矿井 A_i 的和为 x，就能算出最大开采量为：

\min(M - \sum_{i=1}^{r-1} C_i, x)

其中 r 表示编号最大的矿井。选前 K 大的数可以考虑用一个堆维护。

电梯接客

此题的关键点：所有乘客目的地相同，因此一次行程中电梯总是从某个起点出发，沿途接人，最后到达 Y。如果行程起点是 Y（即之前已返回过顶层），则这次行程的时间为 2 \times (Y - L)，其中 L 是该行程中到达的最低楼层（因为要从 Y 下到 L 再返回 Y）。第一次行程起点为 X，时间为 |X - L| + (Y - L)。

贪心策略

将请求按楼层从小到大排序。然后每次从最低楼层开始依次接人，直到接完 W 人为止。如果暴力模拟上述过程，时间复杂度 O(\sum_{}^{}A_i)，需要优化。我们可以维护当前电梯内已有的人数 now 和当前尚未处理的最低楼层 st（即当前行程将要到达的最低楼层）。对于当前楼层 i：

如果 now + A_i < W，则将这一层的人全部加入电梯，继续下一层。

否则，说明电梯将满，需要送一趟。这一趟将带走电梯里已有的 now 人以及当前楼层的 W-now 人，使电梯满载。 然后更新当前楼层剩余人数，并计算该楼层剩余人数需要 \lfloor A_i/W \rfloor 次额外的往返，最后更新 now = A_i \mod W，并将 st 设为当前楼层（如果还有剩余）或下一层。

贪心策略的证明

考虑任意一个最优解，将其行程按最低楼层从小到大排序。设贪心算法得到的行程分组为 G_1, G_2, \dots, G_k，其中 G_1 包含最低的若干楼层，G_2 包含接下来的楼层，以此类推，且每组人数不超过 W，且除 G_k 外每组人数均为 W（或尽可能满）。

假设最优解与贪心不同，则存在第一个行程 G_1'，其最低楼层与贪心相同，但人数少于 W，且它没有包含贪心中 G_1 所包含的某个更高楼层 f（f > \min G_1）。那么 f 一定在最优解的某个后续行程 G_j' 中（j>1）。考虑将 f 的一部分人（或全部）从 G_j' 移到 G_1'，只要不超载。移动后：

$G_j'$ 可能失去一些乘客，若 $f$ 是 $G_j'$ 的最低楼层，则移走后 $G_j'$ 的最低楼层升高（或变为空），其时间减少或不变；若 $f$ 不是最低，则时间不变。 因此总时间不会增加。重复这样的调整，直到 $G_1'$ 包含贪心中 $G_1$ 的所有楼层且人数达到 $W$（或无法再移入）。继续对下一个行程进行同样调整，最终可将最优解转化为贪心解，且时间不增。故贪心最优。 ### 彩色装饰 题意简述 对于每个整数 $k \in [1,m]$，求出 $\sum_{1 \le l \le r \le n}f(l,r,k)$，其中 $f(l,r,k)$ 表示将 $a$ 数组的 $[l,r]$ 区间中所有数都变为 $k$ 后，整个数组的颜色段数。 解题思路 考虑将 $f(l,r,k)$ 对应的式子写出来。将 $[l,r]$ 区间变成 $k$ 会导致数组被分成三个部分：$[1,l-1],[l,r],[r+1,n]$。 想到分别计算三个部分的贡献，并将其相加。$[l,r]$ 区间显然是单独的一段；$[1,l-1]$ 和 $[r+1,n]$ 则分别是前缀和后缀，其贡献可以分别预处理。特别地，如果 $a_{l-1} = k$，那么它所在的段会和 $[l,r]$ 这一段合并在一起，答案 $-1$；如果 $a_{r+1} = k$ 亦然。 由此，$f(l,r,k) = A_{1,l-1} + A_{r+1,n} + 1 - [a_{l-1} = k] - [a_{r+1} = k]$，其中 $[]$ 为艾弗森括号，$A_{l,r}$ 表示 $[l,r]$ 区间的颜色段数；特别地，$A_{1,0} = A_{n+1,n} = 0$，$a_0$ 和 $a_{r+1}$ 不具有任何颜色。 由此，$\sum \limits_{1 \le l \le r \le n}f(l,r,k) = \sum \limits_{1 \le l \le r \le n}(A_{1,l-1} + A_{r+1,n} + 1 - [a_{l-1} = k] - [a_{r+1} = k])$。可以用乘法分配律把式子拆开，然后分别计算每一项的贡献。 - $\sum \limits_{1 \le l \le r \le n} A_{1,l-1} = \sum \limits_{l=1}^{n}(n-l+1) A_{1,l-1} = \sum \limits_{i=1}^{n} (n-i)A_{1,i}$。 - $\sum \limits_{1 \le l \le r \le n} A_{r+1,n} = \sum \limits_{r=1}^{n}r A_{r+1,n} = \sum \limits_{i=1}^{n} (i-1)A_{i,n}$。 - $\sum \limits_{1 \le l \le r \le n} 1 = \frac{n(n+1)}{2}$。 - $\sum \limits_{1 \le l \le r \le n}[a_{l-1} = k] = \sum \limits_{l=1}^{n}(n-l+1)[a_{l-1} = k] = \sum \limits_{i=1}^{n}(n-i)[a_i = k]$。 - $\sum \limits_{1 \le l \le r \le n}[a_{r+1} = k] = \sum \limits_{r=1}^{n}r [a_{r+1} = k] = \sum \limits_{i=1}^{n} (i-1)[a_{i} = k]$。 由此原式子即可简化为： $$\sum_{i=1}^{n} (n-i)A_{1,i} + \sum_{i=1}^{n} (i-1)A_{i,n} + \frac{n(n+1)}{2} + (n-1)\sum_{i=1}^{n}[a_i = k]$$ 前三项是每次询问公共的，可以在最开始预处理出 $A_{1,i}$ 和 $A_{i,n}$ 后跑出。最后一项即 $(n-1)cnt_k$，预处理出是容易的。 ### 树上检查 首先 $k\le 2$ 的部分是简单的，考虑 $k=3,4$ 的部分。 当 $k=3,4$ 时，发现答案一定 $\le 2$，因为一条简单路径可以经过至少 $2$ 个检查点。答案为 $2$ 的数量不好统计，所以考虑统计答案为 $1$ 的数量，不难发现这就是对检查点在一条链上的计数。 设这条链的长度为 $x$，则对答案为 $1$ 的数量的贡献为 ${{x-1}\choose{k-1}}$。枚举链的两端可以做到 $\mathcal O(n^2\log n)$ 或 $\mathcal O(n^2)$，可以获得 $15\sim 35$ 分。 考虑优化，记 $f_{u,i}$ 表示链的一段在 $u$ 的子树中，并且链经过 $u$，已经确定有 $i$ 个检查点的方案。转移是简单的。 统计答案可以考虑枚举以 $u$ 为分界点的两段分别有多少检查点。注意处理是否选 $u$ 以及一个端点为 $u$ 的情况。