2024年第十五届蓝桥杯省赛C++B组(浙江省第二次,4月21号)【真题解析】 |
您所在的位置:网站首页 › 蓝桥杯成绩什么时候出来 › 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(l5->7->5 4,->5->7->5 可以发现是没有区别的,可以直接进行模拟。 这里需要注意的是不需要每次访问就直接替换,可以先把替换到哪里累加下来,比如大三次,小一次,那就是大两次。 最后用埃式筛预处理10w以内的所有素数,如果最后的变换超过了10w的范围,或者变成负数,直接变成0或者1就可以了。 因为素数筛出来是有序的,可以二分先找到 第一个大于 a[i]的素数,然后下标加上 最后累计的次数(注意判断范围,要减一),就是目标结果,负数也一样,注意最后累加值是负数,最后不是减一是加一。 总复杂度nlogn,应该能过 吐槽: 代码能力要求有点高,但凡看错一个细节可能就没分了,甚至还没直接暴力拿的分高。 最后祝愿大伙都拿高分。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |