2023年第十四届蓝桥杯大赛软件类省赛C/C++研究生组真题(代码完整题解)

C题-翻转⭐

标签：贪心

简述：如果 S 中存在子串 101 或者 010，就可以将其分别变为 111 和 000，操作可以无限重复。最少翻转多少次可以把 S 变成和 T 一样。

链接： 翻转

思路：要求步骤最少->S每个位置最多修改一次->从头开始遍历不匹配就翻转->翻转不了就-1

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051233

D题-阶乘的和⭐⭐⭐

标签：STL-map

简述：满足 m! 为 sum(Ai!) 的因数的最大的 m 是多少

链接： 阶乘的和

思路：统计每个阶乘的个数,记录最小的阶乘（记为maxv）。从最小的阶乘开始计算统计maxv的个数是否为(maxv+1)的倍数，如果是则进位 比如$3!+3!+3!+3!+3!+3!+3!+3!=8\ast 3!=2\ast 4!$ 相当于4!增加了两个，向上循环执行该操作即可，如果不是那么就可以break了

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051233

E题- 公因数匹配⭐⭐⭐

标签：数论-质因数

简述：找出最早出现两次质因数的位置

链接：公因数匹配

思路：考虑到 $a_i$ 很小，所以首先预处理出1 ~ 1000000 所有素数，然后对于每个素数枚举其倍数，算出每个数的质因子，这里时间和空间复杂度大概是 $O(loglogn)$，然后对于每个 $a_i$ 枚举其质因子，然后看之前是否有数有相同质因子即可。最后排序输出答案

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051233

F题-奇怪的数⭐⭐⭐⭐

标签：数论-位运算

简述：长为n的数奇数位为奇数偶数位为偶数，任意连续5个数和不大于m有多少个这样的数

链接：奇怪的数

思路：令 $f_{i,a,b,c,d}$ 表示长度为 i 且后四位为 abcd 的奇怪的数的个数，初始化时暴力计算 $f_{5,a,b,c,d}$
f i + 1 , a , b , c , d = ∑ e ≤ m − a − b − c − d f i