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

ops/2024/12/30 4:45:42/

目录

一.[蓝桥杯 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.ppmy.cn/ops/143787.html

相关文章

Java-31 深入浅出 Spring - IoC 基础 启动IoC XML与注解结合的方式 配置改造 applicationContext.xml

Java-31 深入浅出 Spring - IoC 基础 启动IoC XML与注解结合的方式 配置改造 applicationContext.xml

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 大数据篇正在更新&#xff01;https://blog.csdn.net/w776341482/category_12713819.html 目前已经更新到了&#xff1a; MyBatis&#xff…
阅读更多...
Mongodb 集群搭建

Mongodb 集群搭建

Mongodb 集群搭建 一、简介 mongodb 集群有三种方式&#xff1a;Master slave 主从模式、Replica Set 副本集模式、Sharding 分片集模式 Master slave 主从模式&#xff1a;主节点写入&#xff0c;数据同步到 Slave 节点&#xff0c;Slave 节点提供数据查询&#xff0c;最大…
阅读更多...
uniapp入门 01创建项目模版

uniapp入门 01创建项目模版

0安装 hbuilder x 标准版 1.创建模版工程 2.创建官方 案例工程 index.uvuewen 文件解析 <!-- 模版 标签 --> <template><view></view></template><!-- 脚本 --> <script>export default {data() {return {}},onLoad() {},methods:…
阅读更多...
【C++】sophus : sim3.hpp 描述了在 3D 空间中的缩放、旋转和平移 (十九)

【C++】sophus : sim3.hpp 描述了在 3D 空间中的缩放、旋转和平移 (十九)

sim3.hpp 文件定义了与 Sim(3) 群相关的类和操作。Sim(3) 群描述了在 3D 空间中的缩放、旋转和平移。以下是对该文件主要内容的总结&#xff1a; 主要类和命名空间 命名空间 Sophus Sophus 命名空间包含了与 Sim(3) 群相关的所有类和函数定义。 类模板 Sim3Base Sim3Base 是一个…
阅读更多...
企业如何通过TDSQL实现高效数据库迁移与性能优化

企业如何通过TDSQL实现高效数据库迁移与性能优化

目录 一. TDSQL概述 二 Oracle到TDSQL迁移 三. MySQL到TDSQL迁移 四. 总结与建议 TDSQL&#xff08;Tencent Distributed SQL&#xff09;是腾讯云推出的分布式数据库服务&#xff0c;提供了高可用、高扩展性的数据存储解决方案&#xff0c;适用于大规模应用场景。TDSQL支持…
阅读更多...
《探索QT 5.14.1：功能、特性与应用全解析》

《探索QT 5.14.1：功能、特性与应用全解析》

《探索QT 5.14.1&#xff1a;功能、特性与应用全解析》 一、QT 5.14.1&#xff1a;强大的跨平台开发利器二、QT 5.14.1 的核心功能与特性&#xff08;一&#xff09;丰富的控件库&#xff08;二&#xff09;高效的信号槽机制&#xff08;三&#xff09;卓越的性能表现&#xff…
阅读更多...
win11 C盘出现感叹号解决方法

win11 C盘出现感叹号解决方法

出现感叹号&#xff0c;原因是对C盘进行了BitLocker驱动器加密操作。如果想去除感叹号&#xff0c;对C盘进行BitLocker解密即可。 步骤如下&#xff1a; 1.点击Windows搜索框 2.搜索框内输入 系统 3.按下回车&#xff0c;进入系统界面 4.点击隐私和安全性 点击BitLocker驱…
阅读更多...
【Graylog】索引别名deflector的异常处理和索引分片数限制解除

【Graylog】索引别名deflector的异常处理和索引分片数限制解除

索引别名deflector的异常处理 官方推荐处理步骤 Stop all Graylog nodes (OPTIONAL) If you want to keep the already ingested messages, reindex them into the Elasticsearch index with the greatest number, e. g. graylog_23 if you want to fix the deflector graylo…
阅读更多...
最新文章

Copyright @ 2022~2023