蓝桥杯——竞赛省赛国赛题分享

目录

一.[蓝桥杯 2013 省 AB] 错误票据

代码如下：

二.[蓝桥杯 2024 省 Java B] 报数游戏

代码如下：

讲解：

三.[蓝桥杯 2014 国 C] 拼接平方数

代码如下：

四.三步问题（递归，上台阶）

代码1（不用递归）

代码2（使用递归）

该代码特色：

往期回顾：

---

一.[蓝桥杯 2013 省 AB] 错误票据

代码如下：

代码如下：
#include <stdio.h>
int main()
{int n = 0, i = 0, j = 0;int g[10005];scanf("%d", &n);while (scanf("%d", &g[i]) != EOF){i++;}int len = i;
//冒泡排序for (i = 0; i < len - 1; i++){for (j = i + 1; j < len; j++){if (g[i] > g[j]){int t = g[i];g[i] = g[j];g[j] = t;}}}int ans1 = 0, ans2 = 0;for (i = 0; i < len; i++){if (g[i + 1] - g[i] == 2)ans1 = g[i] + 1;if (g[i] == g[i + 1])ans2 = g[i];}printf("%d %d", ans1, ans2);return 0;
}

虽然是二维数组，但是可以看成一维，

题解中冒泡排序是解答关键！！！！！！

二.[蓝桥杯 2024 省 Java B] 报数游戏

代码如下：

int gcd(int a, int b)
{long long temp;long long temp1;long long n ;while (b != 0){n = a % b;temp = a;a = b;b = temp;temp1 = b;b = n;n = temp1;}return a;
}
int main()
{long long n = 0;n = 20*24/gcd(20, 24);long long m = 202420242024 / 10*n;long long i = 0;while (i<5){if (m % 20 == 0 || m % 24 == 0){i++;}m ++;}m--;printf("%lld", m);return 0;
}

讲解：

先通过gcd函数（辗转相除法）求出最大公约数，再利用公式a * b / gcd(a, b)求出最小公倍数，20 和 24 的最小公倍数是 120。

这意味着每 120 个数里，是 20 或 24 倍数的数有一定规律且数量是固定的。在区间[1, 120]内，是 20 倍数的数有120 / 20 = 6个（分别是 20、40、60、80、100、120），是 24 倍数的数有120 / 24 = 5个（分别是 24、48、72、96、120），但其中 120 重复计算了一次，所以在每 120 个数里，满足条件的数共有6 + 5 - 1 = 10个。

1. 批量计算
   利用这个规律，可以批量跳过一些区间来快速逼近第 202420242024 个符合要求的数。比如，已经知道每 120 个数里有 10 个符合要求的数，那么可以先计算出完整的 “120 个数区间” 的个数，即202420242024 / 10 = 20242024202（这里只取整数部分）个这样的区间。

这意味着前面已经处理了20242024202 * 120 = 2429042904240个数，此时还剩下一定数量的数要继续找，可以通过202420242024 % 10算出还需要在后续区间里找几个符合要求的数（余数为 4，表示还需要找 4 个）。

然后从2429042904240 + 1开始继续按顺序找剩下的数，直到找到 4 个符合要求的数为止，这样相比逐个数字去判断是否符合要求，可以大大减少循环次数，节省时间。

细节问题！！！：

循环结束m--；当i符合条件的时候，m会又自增一下。

虽然要再找4个，但是要i<5，因为开始进入一定符合但是不能算起始那个，因此要循环五次

三.[蓝桥杯 2014 国 C] 拼接平方数

代码如下：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>// 计算数字的位数
int slen(int n)
{int len = 0;while (n > 0){n = n / 10;len++;}return len;
}// 判断一个数是否为拼接平方数
int is_spliced_square(int num)
{int len = slen(num);for (int split_pos = 1; split_pos < len; split_pos++){// 分割数字为两部分int part1 = num / (int)pow(10, split_pos);int part2 = num % (int)pow(10, split_pos);// 排除 0、00 等无效数字情况if (part1 == 0 || part2 == 0){continue;}int part1_sqrt = (int)sqrt((double)part1);int part2_sqrt = (int)sqrt((double)part2);if (part1_sqrt * part1_sqrt == part1 && part2_sqrt * part2_sqrt == part2){return 1;}}return 0;
}int main()
{int a = 0;int b = 0;int i1 = 0;int i2 = 0;if (scanf("%d%d", &a, &b) != 2){printf("输入格式有误，请重新输入两个整数\n");return 1;}// 遍历区间内的所有数字进行判断并输出for (int i = a; i <= b; i++){i1 = (int)sqrt(i);if (i1 * i1 != i){continue;}else{if (is_spliced_square(i)){printf("%d\n", i);}}}return 0;
}

（注意：拼接平方数首先自己得是平方数！！！）

四.三步问题（递归，上台阶）

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3

 输出：4

 说明: 有四种走法

示例2:

 输入：n = 5

 输出：13

提示:

1. n范围在[1, 1000000]之间

核心思想：

当 n > 3 时，进入这个 for 循环，从 i = 4 开始，逐步计算上 i 阶楼梯的走法数量。

递推关系的核心在于 a = (s1 + s2 + s3) % 1000000007; 这一行。对于上 i 阶楼梯（i > 3），最后一步可能是走了 1 阶（那么前面 i - 1 阶的走法数量就是 s1）、走了 2 阶（前面 i - 2 阶的走法数量是 s2）或者走了 3 阶（前面 i - 3 阶的走法数量是 s3），根据加法原理，上 i 阶楼梯的总走法数量就是上 i - 1 阶、i - 2 阶、i - 3 阶楼梯走法数量之和，即 s1 + s2 + s3。同时，为了满足题目对结果取模的要求，这里直接对相加的结果取模 1000000007 后赋值给 a，a 就代表上 i 阶楼梯的走法数量（取模后）。

代码1（不用递归）

int waysToStep(int n){long long int s1=1,s2=2,s3=4,a=0,b,c;if(n<=3){switch(n){case 1:a=s1;break;case 2:a=s2;break;case 3:a = s3;break;}}else{for(int i=4;i<=n;i++){a = (s1+s2+s3)%1000000007;b = s3;s3 = a;c = s2;s2 = b;s1 = c;}}return a;}

代码2（使用递归）

#include <stdio.h>
#include <stdlib.h>// 定义一个足够大的数组用于存储已经计算过的结果，避免重复计算，初始化为 -1 表示未计算过
long long int memo[1000001];// 递归函数结合记忆化来计算上n阶楼梯的走法数量，取模操作按照题目要求进行
long long int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;// 如果已经计算过该值，直接返回存储的结果，避免重复计算if (memo[n]!= -1) return memo[n];long long int result = (waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3)) % 1000000007;// 将计算结果存储到备忘录数组中memo[n] = result;return result;
}
int main() {// 初始化memo数组为 -1，表示都未计算过for (int i = 0; i < 1000001; i++) {memo[i] = -1;}int n = 61;long long int ways = waysToStep(n);printf("上 %d 阶楼梯的走法数量（取模后）为：%lld\n", n, ways);return 0;
}

该代码特色：

数组的记忆使用避免了代码重复运算

1. 为什么会出现重复计算（以纯递归情况分析）

在不使用数组进行优化的纯递归解决 “三步问题” 的过程中，存在大量重复的子问题计算。例如，当我们要计算 waysToStep(5) 时，按照递归关系：

隐藏过程

long long int result = (waysToStep(4) + waysToStep(3) + waysToStep(2)) % 1000000007;

需要先去计算 waysToStep(4)，而计算 waysToStep(4) 时又会按照它的递归关系：

隐藏过程

long long int result = (waysToStep(3) + waysToStep(2) + waysToStep(1)) % 1000000007;

再次去计算 waysToStep(3) 和 waysToStep(2) 以及 waysToStep(1)。注意这里的 waysToStep(3) 和 waysToStep(2) 在计算 waysToStep(5) 时已经计算过一次了，但是纯递归的方式没办法记住这个结果，所以就会重复地去调用函数计算它们。

同样地，在后续计算更大的 n 值时，像 waysToStep(2) 和 waysToStep(3) 这样的基础子问题会被反复地计算很多很多次，随着 n 的增大，这种重复计算的次数会急剧增加，导致效率变得极低，白白浪费了很多计算资源。

（1）memo 数组的定义和初始化

首先，定义了一个数组 memo 来存储已经计算过的结果，代码如下：

展开过程

这里把 memo 数组的每个元素初始化为 -1，是为了表示对应位置（也就是对应 n 值）的上楼梯走法数量还没有被计算过，后续通过判断元素的值是否为 -1 就能知道是否需要重新计算。

（2）在递归计算过程中的使用

在 waysToStep 函数内部，每次要进行递归计算之前，会先检查 memo 数组中对应位置的值，代码如下：

隐藏过程

if (memo[n]!= -1) return memo[n];

这行代码的意思是，如果 memo[n] 的值不等于 -1，那就说明之前已经计算过了上 n 阶楼梯的走法数量，并且已经把结果存储在了 memo[n] 这个位置，此时就不需要再去重复地通过递归调用计算了，直接返回 memo[n] 存储的结果就行，这样就避免了重复计算已经算过的子问题。

而当发现 memo[n] 是 -1，也就是还没有计算过时，才会按照正常的递归关系去计算上 n 阶楼梯的走法数量，计算完之后，会把结果存储到 memo[n] 中，方便下次再遇到同样的 n 值时直接获取，代码如下：

隐藏过程

long long int result = (waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3)) % 1000000007;

memo[n] = result;

return result;

通过这样的方式，在整个递归调用的过程中，对于每个 n 值，最多只需要计算一次其对应的上楼梯走法数量，后续再次需要这个值时，直接从 memo 数组中获取，大大减少了不必要的计算，提高了代码的执行效率，尤其是当 n 的值比较大或者频繁调用 waysToStep 函数时，这种优化效果会更加明显。

往期回顾：

C语言——结构体（超详解）-CSDN博客

C语言——判断输入字符串是否合法代码分享-CSDN博客

C语言——字符串指针变量与字符数组（易错分析）-CSDN博客

C语言——习题练习（一）-CSDN博客

C语言——海龟作图（对之前所有内容复习）_海龟图c语言-CSDN博客

C语言函数递归经典题型——汉诺塔问题_汉诺(hanoi)塔问题-CSDN博客

C语言算法经典基础题型——求一个数的回文数（两种方法）_c语言编程题回文数-CSDN博客