本文主要是介绍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，应该能过
吐槽：
代码能力要求有点高，但凡看错一个细节可能就没分了，甚至还没直接暴力拿的分高。
最后祝愿大伙都拿高分。
这篇关于2024年第十五届蓝桥杯省赛C++B组（浙江省第二次，4月21号）【真题解析】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
