蓝桥杯第十五届抱佛脚（一）手算和思维题

本文主要是介绍蓝桥杯第十五届抱佛脚（一）手算和思维题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蓝桥杯第十五届抱佛脚（一）手算和思维题

比赛流程

• 赛程：

  • 2024年4月13日：省赛

  • 决赛

    省赛一等奖参加决赛

    比赛时长 4小时（9:00—13:00）

• 竞赛形式：

  • 个人赛，一人一机，全程机考

  • 答题过程中无法访问互联网

  • 不允许携带任何电子、纸质资料

• 参赛选手机器环境

  • X86 兼容机器，内存不小于 1G，硬盘不小于 60G 操作系统：Windows7、Windows8 或 Windows10。

  • C/C++ 开发环境：Dev-cpp 5.11 C/C++ API 帮助文档

  • Java 开发环境：JDK 1.8 Eclipse-java-2020-06 API 帮助文档

  • Python 环境：Python 3.8.6 IDLE（Python 自带编辑器）

• 题型

  • 结果填空 把答案直接通过网页提交，不要书写多余的内容。填空题每题 5 分。

  • 程序设计 每道题目多个测试数据，20%∼40% 是弱测试数据，其他是强测试数据。

    • 题量大、时间紧张，难题往往不会做或来不及用高效算法编码，此时可以用暴力方法编程得 20%∼40%的分数。
    • 程序设计题每题10% 25%分。

• 评分方式

  • 评分：全部使用机器自动评分

对于结果填空题，题目保证只有唯一解，选手的结果只有和解完全相同才得分，出现格式错误或有多余内容时不得分。

对于编程大题，评测系统将使用多个评测数据来测试程序。每个评测数据有对应的分数。选手所提交的程序将分别用每个评测数据作为输入来运行。对于某个评测数据，如果选手程序的输出与正确答案是匹配的，则选手获得该评测数据的分数。

知识点梳理

• 思维题（杂题）：不需要算法和数据结构，只需要逻辑、推理的题目，难度可难可易。考察思维能力和编码能力，只能通过大量做题来提高。
• BFS 搜索和 DFS 搜索：也就是暴力搜索。这是非常基本的算法，是基础中的基础。
• 动态规划：线性 DP，以及一些 DP 应用，例如状态压缩 DP、树形 DP 等。
• 简单数学和简单数论。
• 简单的字符串处理、输入输出，简单图论。
• 基本算法：例如排序、排列、二分、倍增、差分、贪心。
• 基本数据结构：队列、栈、链表、二叉树等。

技巧：手算

• 应用场合

  • 填空题

• 手算的目的

  • 减少做题时间，省下时间做编程题。

• 手段：

  • 不编码，或者只做部分编码
  • 用推理获得答案
  • 用软件工具帮助计算

• 方法：

  • 巧用编辑器

  • 心算手数

  • 巧用 Excel

  • 巧用 Python

1. 门牌制作 2020 年第十一届蓝桥杯省赛，填空题

正常解决

public class CountDigitTwo {public static void main(String[] args) {int count = 0;for (int i = 1; i <= 2020; i++) {count += countDigitTwo(i);}System.out.println("从1到2020中,共有" + count + "个2");}public static int countDigitTwo(int num) {int count = 0;String numStr = String.valueOf(num);for (int i = 0; i < numStr.length(); i++) {if (numStr.charAt(i) == '2') {count++;}}return count;}
}

巧解

• 先编码连续打印出 1 ∼ 2020 这 2020 个数字

• 然后把输出结果粘贴到word中，按下 Ctrl + F

• 查找或替换字符 “2”，共 624 次，就是答案。
  

2. 迷宫 2017 年第八届蓝桥杯省赛，填空题

正常解决

• DFS 搜索

public class MazeSolver {static char[][] arr; // 存储迷宫信息的二维字符数组static int[][] vis; // 记录每个位置是否被访问过的二维整型数组static int ans = 0; // 记录能够走出迷宫的人数public static void main(String[] args) {Scanner sc = new Scanner(System.in);arr = new char[10][10]; // 初始化迷宫数组for (int i = 0; i < arr.length; i++) {String s = sc.next(); // 从控制台读取一行迷宫数据arr[i] = s.toCharArray(); // 将字符串转换为字符数组,存储到迷宫数组中}for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[0].length; j++) {vis = new int[10][10]; // 初始化访问记录数组dfs(i, j); // 从当前位置开始进行深度优先搜索}}System.out.println(ans); // 输出能够走出迷宫的人数}public static void dfs(int x, int y) {if (x <= -1 || y >= 10 || x >= 10 || y <= -1) { // 检查是否超出迷宫边界ans++; // 如果超出边界,说明可以走出迷宫,将ans加1return;}if (vis[y][x] == 1) { // 如果当前位置之前已经被访问过return; // 直接返回,不需要继续搜索}vis[y][x] = 1; // 标记当前位置为已访问if (arr[y][x] == 'U') { // 如果当前位置指示牌指向上dfs(x, y - 1); // 向上移动一步,继续搜索}if (arr[y][x] == 'D') { // 如果当前位置指示牌指向下dfs(x, y + 1); // 向下移动一步,继续搜索}if (arr[y][x] == 'L') { // 如果当前位置指示牌指向左dfs(x - 1, y); // 向左移动一步,继续搜索}if (arr[y][x] == 'R') { // 如果当前位置指示牌指向右dfs(x + 1, y); // 向右移动一步,继续搜索}}
}

巧解

• 直接用手画图标记 3-5 分钟。一共31个人可以走出来和上面编码是一样的答案。

  ↑ ↓ ↓ ← ↑ ↑ ← → ↑ ←  7↑ ↑ → ← ← ← → → → ↑  5→ → ↑ ↑ → ← ↓ ← → ↓  0→ ↑ ↓ ↓ ↓ ↓ ↑ ↑ ↑ ↑  0↑ → ↑ ↓ ← ← → → ↑ ↑  0↓ ↑ → ← → ← ↓ ← → ←  0↑ ← ← ↑ → ← ← → ↓ ↑  2→ ↓ ← ↑ ← ← → ↓ ↓ ↓  4↑ ↑ ↓ ↓ ↑ ↓ ↑ ↓ ← ←  6↑ ← → ↓ ← ↑ ↑ → → →  7

3. 星期一 2018 年第九届蓝桥杯省赛，填空题

正常解决

• 首先,我们使用Calendar类设置起始日期为1901年1月1日,结束日期为2000年12月31日。
• 初始化一个变量mondayCount来统计星期一的个数。
• 使用for循环遍历1901年1月1日到2000年12月31日之间的每一天。

import java.util.Calendar;public class CountMondays {public static void main(String[] args) {// 设置起始日期为1901年1月1日Calendar startDate = Calendar.getInstance();startDate.set(1901, 0, 1);// 设置结束日期为2000年12月31日Calendar endDate = Calendar.getInstance();endDate.set(2000, 11, 31);int mondayCount = 0;// 遍历每一天,判断是否为星期一for (Calendar date = (Calendar) startDate.clone(); date.compareTo(endDate) <= 0; date.add(Calendar.DATE, 1)) {if (date.get(Calendar.DAY_OF_WEEK) == Calendar.MONDAY) {mondayCount++;}}System.out.println("20世纪一共有" + mondayCount + "个星期一");}
}

巧解

• 用 Excel，在一个格子里输入日期 1901 年 1 月 1 日，另一个格子输入 2000 年 12 月 31 日，然后两个格子相减得 36524 天，除以 7 得 5217.7 周。

• 再看 1901 年 1 月 1 日是星期几。

• 用 Excel 点 1901 年 1 月 1 日这一格的“设置单元格式-数字-日期-星期三”，点击“确定”，得“星期二”，即 1901 年 1 月 1 日是星期二，36524 是 5217 周多几天，最后几天没有星期一，说明答案就是 5217。
  

巧用 Python

填空题遇到字符、大数字、日期问题，Python 是首选。

• 即使参加 C/C++、Java 组比赛，也要学一些 Python，以方便手算，或用来做对比测试。

• 这几种语言的编译器，在比赛机器上都有。

• 写 Python 代码既简单又快，代码长度一般比 C/C++、Java 短很多。例如 30 行的 C++代码，用 Python 写只需要 20 行。

3. 星期一 2018 年第九届蓝桥杯省赛，填空题

from datetime import*
dt1=datetime(1901,1,1)
dt2=datetime(2000,12,31)print(dt1.weekday())
# 周一为0，周二为1...td=dt2-dt1print(td.days//7)

4. 乘积尾零 2018 年第九届蓝桥杯省赛，填空题

nums_str = "5650 4542 3554 473 946 4114 3871 9073 90 4329 2758 7949 6113 5659 5245 7432 3051 4434 6704 3594 9937 1173 6866 3397 4759 7557 3070 2287 1453 9899 1486 5722 3135 1170 4014 5510 5120 729 2880 9019 2049 698 4582 4346 4427 646 9742 7340 1230 7683 5693 7015 6887 7381 4172 4341 2909 2027 7355 5649 6701 6645 1671 5978 2704 9926 295 3125 3878 6785 2066 4247 4800 1578 6652 4616 1113 6205 3264 2915 3966 5291 2904 1285 2193 1428 2265 8730 9436 7074 689 5510 8243 6114 337 4096 8199 7313 3685 211 "nums = [int(num) for num in nums_str.split()]def count_trailing_zeros(nums):product = 1for num in nums:product *= numtrailing_zeros = 0while product % 10 == 0:trailing_zeros += 1product //= 10return trailing_zerosprint(f"乘积的末尾有 {count_trailing_zeros(nums)} 个零")

思维题

• 不需要涉及某种算法的题目。
• 只要学过编程语言，就能够解答。
• 主要考核学生的思维、逻辑和编码能力，强调脑筋急转弯的解决方式。
• 这类题目包括模拟题、构造题、思维题以及找规律题，统称为“思维题（杂题）”。
• 每年蓝桥杯都会设置这类题目，而且可能有多道，是考试中的重要得分点。
• 杂题涵盖了各种难度，有些可能相对简单，而另一些可能相对较难。

5. 付账问题 2018 年第九届蓝桥杯省赛，OJ题

import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String args[]) {int n; // 存储人数long S; // 存储总金额double ans=0,avg; // ans存储最终的标准差结果,avg用于存储平均值Scanner input=new Scanner(System.in);n=input.nextInt();S=input.nextLong();long a[]=new long[n]; // 存储每个人携带的金额for(int i=0;i<n;i++) a[i]=input.nextLong();Arrays.sort(a);avg=(double)S/n; for(int i=0;i<n;i++) { if(S<=(n-i)*a[i]) { // 如果剩余金额小于等于(人数-i)*(第i个人的金额)ans += (n-i)*Math.pow((double)S/(n-i)-avg,2); // 计算最后(n-i)个人的贡献,并加入ansbreak; // 跳出循环}ans += Math.pow(a[i]-avg,2); // 计算第i个人的贡献,并加入ansS -= a[i]; // 从剩余金额S中扣除第i个人的金额}System.out.printf("%.4f\n",Math.sqrt(ans/n)); // 输出标准差结果,保留4位小数}
}

练习题

6. 阶乘求和 2023年第十四届蓝桥杯省赛，填空题

解决思路1：

1. 首先，我们需要一个方法来计算阶乘，以及一个方法来计算阶乘的和。因为数值可能很大，我们需要考虑取模运算来避免溢出。
2. 编写一个方法来计算阶乘。在这个方法中，使用循环从1到给定的数字n，逐步计算阶乘，并在每一步进行取模操作，以避免数值溢出。
3. 编写另一个方法来计算阶乘的和。在这个方法中，对于给定的起始和结束数字，依次计算每个数字的阶乘，并累加到总和中。同样，每一步都要进行取模操作。
4. 最后，调用计算阶乘和的方法，将结果输出。

public class FactorialSum {public static long INF = 10000000000L;public static void main(String[] args) {long sum = 0;for (int i = 1; i <= 40; i++) {sum = sum + fact(i);}System.out.println(sum % 1000000000);}public static long fact(int n) {long sum1 = 1;for (long i = 1; i <= n; i++) {sum1 = sum1 * i;if (sum1 >= INF) sum1 = sum1 % INF;}return sum1;}
}

解决思路2：

• 直接用Java的BigInteger类

Java中的BigInteger类是用于表示任意精度整数的类。它可以处理比Java中的原生整数类型（如int、long）更大的整数，因为它不受原生整数类型的大小限制。

下面是关于BigInteger类的一些重要信息：

1. 表示范围：BigInteger类可以表示任意大小的整数，只受系统内存限制。

2. 不可变性：BigInteger对象是不可变的，即一旦创建了一个BigInteger对象，就无法修改它的值。任何对BigInteger对象进行的操作都会返回一个新的BigInteger对象。

3. 构造方法：可以使用多种方式创建BigInteger对象，包括传入字符串表示的整数、传入字节数组表示的整数、以及使用原生整数类型表示的整数等。

4. 常用方法：

   • add(BigInteger val)：返回两个BigInteger对象的和。
   • subtract(BigInteger val)：返回两个BigInteger对象的差。
   • multiply(BigInteger val)：返回两个BigInteger对象的乘积。
   • divide(BigInteger val)：返回两个BigInteger对象的商。
   • mod(BigInteger val)：返回BigInteger对象除以指定值后的余数。
   • pow(int exponent)：返回BigInteger对象的指数幂。
   • compareTo(BigInteger val)：比较两个BigInteger对象的大小。
   • toString()：将BigInteger对象转换为字符串表示形式。

5. 支持的运算：BigInteger类支持大整数的加减乘除、幂运算、取模运算等各种运算操作。

6. 性能：由于BigInteger类是为了处理大整数而设计的，因此在执行大整数运算时会比原生整数类型的运算慢。

7. 应用场景：BigInteger类通常用于需要处理非常大的整数，例如加密算法、大整数计算、数论等领域。

BigInteger类是Java中用于处理任意精度整数的重要类之一，它提供了丰富的方法来进行大整数的各种运算操作，并能够处理超出原生整数类型表示范围的大整数。

import java.math.BigInteger;public class FactorialSum2 {public static void main(String[] args) {BigInteger sum = BigInteger.valueOf(0);//初始化0for(int i = 1; i <= 40; i ++) {BigInteger sum1 = BigInteger.valueOf(1);for(int j = 1; j <= i; j ++) {sum1 = sum1.multiply(BigInteger.valueOf(j));//乘法}sum = sum.add(sum1);}System.out.println(sum);//最后复制最后九位数即是答案。}
}

这篇关于蓝桥杯第十五届抱佛脚（一）手算和思维题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！