2024年第十五届蓝桥杯省赛C++B组（浙江省第二次，4月21号）【真题解析】

阅读本书更多章节>>>>

等C语言网或者别的地方更新题目，蓝桥杯真题 - 编程题库 - C语言网 (dotcpp.com)，后序再做更新

题目没带出来有点忘了，下面是不按顺序来的

第一题：一个数被表达成别的数，是否会出现字母。

除进制取余，进制转换暴力一下，看看哪个进制没有>10的出现

应该是：32

第二题：逆序对期望：n=51

1 2 3 4 5 .... 51，任意选择 i 和 j，i≠j，交换。

随机执行两次交换，逆序对的数量期望是几个。

可以枚举所有交换，然后再暴力比较有几个逆序对（不需要归并，n*n也不是很慢，反正是填空题），就能求出总方案。

在概率论和统计学中，数学期望(mathematic expectation [4])（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。

所以应该只需要总逆序对求和，除以枚举的次数就行。答案忘了

第三题：传送门

对于序列c[i]，代表 i 传送门可以传向 c[i] 传送门

可以执行一次魔法：从i传送门到 i-1传送门 或者 i+1传送门

问最多可以走过几个不同的传送门。

应该就是一个并查集，所有的传送门块分到一起，然后遍历一次应用一下魔法，标记出块与块之间的连通性。

最后枚举所有块本身和块+块是否能使用魔法，累计答案。

第四题：字符串

给你n个字符串，你可以执行一次操作：修改其中的一个字符串中的一个字符。

问任意两对串最长公共前缀的和是多少，如s1="abc",s2="abd"，这俩的公共前缀长度是2

不超过200个字符串，长度也不超过200

不会，直接暴力的。

考虑枚举每个字符串的每个位置，并且只枚举n个字符串中出现过的字符。

求一次和复杂度：4e4

枚举每个位置：4e4

总复杂度16e8，爆了，应该要优化。

考虑任意一个字符串，如果前面的某一个位置改变之后，不能带来更好的答案，那么改当前这个字符串的这个位置的更后面，也不会有更优解。这样优化之后可能刚好通过题目。

第五题：字符串

遗迹键盘

比如有以下字符串

S="abc"

T="abcabcbb"

S是你的键盘，T是你要输出的内容。

刚开始你可以选择S的任意一个位置，然后执行操作：左右移动你的位置，或者输出。

总的移动距离超过 L ，你最多可以输出几位内容。

不会，暴力的 ：）

考虑你的键盘可能会重复出现按钮，所以搜索的时候相同的都要搜  ：（，直接 TLE 飞出去。

因为能重复搜索，也和之前的记忆有关，所以这道题大概率是个dp，本蒟蒻不会。

第六题：狡兔K窟

地上有5000个出入口，地下也有5000个洞窟（最多），每个出入口对应某个洞窟。

即一个洞窟可能有多个出入口。

问，从出入口 S，到出入口 T，地上最短距离是多少（地上出入口连边的长度都是 1）。

如果 S 和 T 连着同一个洞窟，那么显然走地下就行了，地上距离是 0。

因为地上边的长度都是 1，所以求最短路使用 BFS，BFS一次复杂度 5e3，5e3个出入口，总复杂度25e6，就可以求出任意两个出入口之间的最短路。

因为考虑到可以走洞窟，那么把入口之间的最短路在每次BFS的时候转化成洞窟之间的最短路。

最后访问做到O（1），应该恰好通过此题。

Dijkstra或者别的最短路算法，复杂度会比BFS多一个log。（技巧：边都相等，或者都相等和边长为0的，使用BFS就能求出最短路）

第七题：题目忘了

题目大意是任意选择 l 和 r（l<=r），要求 a[l]，a[r] 均大于 a[l-1 ~ r-1] 他们中间的值，求最大的 r-l+1

当时题目分析错了，还以为左边降序右边升序，实际上内部无序也行，只要满足条件。

n^3：考虑暴力枚举左右端点，暴力枚举端点中间的最大值，判断是否可行。

n^2*logn：考虑暴力枚举左右端点，内部区间最大值用线段树来维护。

n^2：没想到，可能还要加个二分。

第八题：素数

对于 i mod k = 0 的 a序列中的值，将他替换成比他大x的质数，或者比他小x的质数。

这里是下标 i 啊，有好多人以为是 a[i] mod k，不是具体的值。

如果最后替换完了之后，质数小于0，那就把它变成0，如果大于10w，就变成1（好像是10w）

首先我们分类讨论一下，质数和非质数的变换是否有区别：

3，先变成比他大2次的质数，再变成比他小一次的质数，->5->7->5

4,->5->7->5

可以发现是没有区别的，可以直接进行模拟。

这里需要注意的是不需要每次访问就直接替换，可以先把替换到哪里累加下来，比如大三次，小一次，那就是大两次。

最后用埃式筛预处理10w以内的所有素数，如果最后的变换超过了10w的范围，或者变成负数，直接变成0或者1就可以了。

因为素数筛出来是有序的，可以二分先找到 第一个大于 a[i]的素数，然后下标加上 最后累计的次数（注意判断范围，要减一），就是目标结果，负数也一样，注意最后累加值是负数，最后不是减一是加一。

总复杂度nlogn，应该能过

吐槽：

代码能力要求有点高，但凡看错一个细节可能就没分了，甚至还没直接暴力拿的分高。

最后祝愿大伙都拿高分。

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-23/161489.html，文章来源：网络cs，作者：纳雷武，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！