当前位置： 首页 > article >正文

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

article 2024/12/23 8:35:20

目录

一.[蓝桥杯 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博客


http://www.kler.cn/a/444091.html

相关文章：

  • APM32F411使用IIS外设驱动es8388实现自录自播
  • 嵌入式硬件面试题
  • 阿里云百炼大模型生成贪吃蛇小游戏
  • 将4G太阳能无线监控的视频接入电子监控大屏，要考虑哪些方面？
  • 信号处理相关的东东（学习解惑）
  • 进网许可认证、交换路由设备检测项目更新25年1月起
  • React中定义和使用函数式组件
  • 天天 AI-241215：今日热点-OpenAI发布ChatGPT Projects，万能工具箱上线！
  • Vue零基础教程|从前端框架到GIS开发系列课程（五）组件式开发
  • Quartz 架构和单体应用介绍
  • 汽车IVI中控开发入门及进阶（三十八）：HiCar开发
  • 数据结构，链表的简单使用
  • UDP基本了解
  • 为什么要用单例模式？
  • windows C#-命名实参和可选实参(下)
  • C/C++语言——解题
  • 机试题——维修工
  • UI框架DevExpress XAF v24.2新功能预览 - .NET Core / .NET增强
  • Flutter控件FutureBuilder控件详解
  • uniapp使用百度地图配置了key,但是显示Map key not configured
  • Unity 根据文本宽度自动移动图像位置
  • thinkphp5命令行，addOption和addArgument有什么区别
  • 51c自动驾驶~合集41
  • 受限前缀注意机制的事件关系识别
  • Spark-Streaming性能调优
  • el-date-picker筛选时间日期选择范围