【CS-LQR-2025】计算机学会2025蓝桥能力提升赛题解

Kendieer · 2024-11-14 01:24:42 · 个人记录

在整体难度上，本次提升赛相比以往的月赛来说简单了不少，相信不少选手已经体会到了。

赛后补题链接: [link]

涉及知识点

以下是这次提升赛涉及到的知识点，其中用 | 隔开的表示另一种做法下涉及到的知识点。

题解思路

A.理想乡

不难发现，两个日期的月份和日期非常相近，所以我们可以先求完整年份的天数，然后 -1 即可(别忘了日期原本就相差一天)。

然后计算一下 2024\sim 2077 中有多少个闰年(不含 2024 年)。

结果就是: 365\times 53 + 13 - 1 = 19357。

答案: 19357

B.RGB

不要总是想着用数学去解这道题，暴力枚举才是家。

可以通过写程序分别枚举每种球的数量，进而得出结果。

答案: 16103

C.感恩之心

暴力枚举 2\sim 1000 所有数字，并判断是否为质数，如果是则累加即可。

什么是质数?建议 BDFS 谢谢。\rarr 素数

判断质数的时候其实不用枚举 2\sim n-1 的，只需枚举 1\sim \sqrt{n} 即可。（当然，你用质数筛当我没说）

答案: 76127

D.染色

不难发现，文件中的坐标范围很大，我们肯定不能正常存储每个格子的内容（就算能存又有什么用，运算时间够你运算等待的）。

那我们不存每个格子的情况，该存什么呢？

其实，我们可以发现每次操作只用知道每段的两个点即可，中间情况其实都是填满的，于是我们就可以考虑离散化了。

我们将所有的起始点和终点存起来，然后按位置排序，然后扫一遍，每当遇到起点则层数 +1，遇到终点则层数 -1，当层数 0\rarr1 时记录起点位置 l，当 1\rarr 0 的时候，该位置看作 r，然后结算当前 [l,r] 的长度。

答案: 996748741

E.失忆

吐槽: 我知道你这题很想用 sort，但是试问你真的会写吗?

不闹了，这题其实所有 O(n^2) 的排序方案都能过，所以暴力排序(例如：冒泡排序、选择排序)也没问题的。

对了，这题因为数据很小，所以可以用计数排序，最优是 O(n+\max{a_i})。

F.决斗

其实这题无论怎么取结果都是一样的，因为每次取值时只会被原数组对应数值有关。

所以这题将其排序后按顺序计算最后总和即可。

G.咖啡矩阵

一道非常接地(di)道(fu)的模拟题，让我的大脑起飞。

这题难点在于理解矩阵乘法。

代码实现上纯粹模拟即可。

H.重构

很明显，一个数字倘若最大化，那么它的最大位一定最大的，以此类推。

于是我们将对应数字从大到小输出前 k 位就行。

可以用排序，也可以直接计数输出即可。

排序方案时间复杂度 O(n\log{n})，计数方案时间复杂度 O(n)。

I.野的枚举

这题暴力难度其实比正解代码难度上会更难qwq

解法A: 动态规划

对于每次前进到 (x,y) 的位置的方案数，可以发现它的数量是到达 (x-1,y) 的方案数与到达 (x,y-1) 的总和。

即 dp_{i,j} = dp_{i,j-1} + dp_{i-1,j}。

时间复杂度为 O(nm)。

解法B: 组合数学

对于到达坐标 (n,m)，我们可以发现它由 n-1 个向 x 正方向行动和 m-1 个向 y 正方向行动。

于是它的组合情况就有 C^{n-1}_{n+m-2}。

PS: C^{k}_{n}=C^{n-k}_{n}

然后还有求组合数的时候无法整除的问题，这里可以提供两种方案参考:

1. 将模数加回来，直到可以整除。(数据很小，可以随便玩)

2. 使用乘法逆元。

时间复杂度: O(n+m)

J.逆袭

解法A: 归并排序

首先你需要知道什么是归并排序。然后，我们可以这样想：

如果我们想要将一个序列排成从小到大有序的，那么每次划分后合并时左右子区间都是从小到大排好序的。

在合并阶段时候，如果右区间的数字比左区间的小，那么就可以知道对于右区间的数字产生的逆序对有左区间剩余数字的数量。

然后正常合并即可。

由于归并排序没有什么坑，正常执行并统计即可。

解法B: 树状数组

对于一个逆序对，我们由定义可得大的数值一定在小的数值后面，于是我们可以根据这个性质进行统计数量。

首先，我们需要准备好逆序对数量表和原数组。

逆序对数量表用于统计当前未插入元素位置有多少对逆序对。

然后，将原数组按升序排序。

每次我们进行一次操作:

删除当前的最小值，并获取该值原位置的逆序对数量(初始为 0 )，并使 1\sim i-1 的逆序对数量 +1，这里用树状数组维护即可。

即使已经插入了元素，由于我们不会再访问该位置，所以对答案无影响。

坑点：相等的元素是否会导致求解错误？

答案是会的，不处理的话会出错的，问题的关键在于是否有与 a_i 相等的元素在 a_i 前被加入且其相对大小标记更大。出现这种情况就会误将两个相等的数判为逆序对。怎么解决呢，只要所有与 a_i 相等的元素中，先出现的标记也更小就好了(我们只统计相对更大的)。具体只需要在排序时将 a_i 作为第一关键字，下标(第几个出现)作为第二关键字从小到大排序即可。

然后就大功告成了。

题解代码

这里代码仅提供以下 3 种语言(对应三条赛道)，如需其他语言可以借助 ChatGPT 等工具转换。

无论是哪种语言都好，建议先看思路再参考，任何题目学习的精髓都是思路而不是代码。

The End