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

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

比赛流程

• 赛程：

  • 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 年第十一届蓝桥杯省赛，填空题

问题描述： 从 1 到 2020 的所有数字中，共有多少个 2？

正常解决

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

巧解

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

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

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

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

问题描述： 给出一个迷宫，问迷宫内的人有多少能走出来。迷宫如右图所示：每个位置上有一个人，共 100 人。每个位置有指示牌，L 表示向左走，R 表示向右走，U 表示向上走，D 表示向下走。

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

正常解决

• 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加1
            return;
        }
        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); // 向右移动一步,继续搜索
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

巧解

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

  ↑ ↓ ↓ ← ↑ ↑ ← → ↑ ←  7
  ↑ ↑ → ← ← ← → → → ↑  5
  → → ↑ ↑ → ← ↓ ← → ↓  0
  → ↑ ↓ ↓ ↓ ↓ ↑ ↑ ↑ ↑  0
  ↑ → ↑ ↓ ← ← → → ↑ ↑  0
  ↓ ↑ → ← → ← ↓ ← → ←  0
  ↑ ← ← ↑ → ← ← → ↓ ↑  2
  → ↓ ← ↑ ← ← → ↓ ↓ ↓  4
  ↑ ↑ ↓ ↓ ↑ ↓ ↑ ↓ ← ←  6
  ↑ ← → ↓ ← ↑ ↑ → → →  7
1
2
3
4
5
6
7
8
9
10

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

问题描述： 整个 20 世纪（1901 年 1 月 1 日至 2000 年 12 月 31 日之间），一共有多少个星期一？

正常解决

• 首先,我们使用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 + "个星期一");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

巧解

• 用 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 年第九届蓝桥杯省赛，填空题

问题描述： 整个 20 世纪(1901 年 1 月 1 日至 2000 年 12 月 31 日之间)，一共有多少个星期一？

直接用 Python datetime 库求解，第 4 行可以输出某个日期是星期几。

from datetime import*
dt1=datetime(1901,1,1)
dt2=datetime(2000,12,31)

print(dt1.weekday())
# 周一为0，周二为1...

td=dt2-dt1

print(td.days//7)
1
2
3
4
5
6
7
8
9
10

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

• 最简单题解：

  • 直接连乘：几千位的大数

  • 然后统计末尾的 0

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 = 1
    for num in nums:
        product *= num

    trailing_zeros = 0
    while product % 10 == 0:
        trailing_zeros += 1
        product //= 10

    return trailing_zeros

print(f"乘积的末尾有 {count_trailing_zeros(nums)} 个零")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思维题

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

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

题目描述：

解决思路：

如果每个人携带的钱足够多，每个人平均支付相同的金额，即 bi = s / n = avg，那么标准差 X 为 0。

然而，总会有人的钱不够，这时我们考虑两种情况：

• 第 i 个人携带的钱不足以达到平均数 avg，那么他只能支付他所携带的全部钱 ai。

• 第 i 个人携带的钱超过平均数 avg，那么他可以支付多一些。

解决步骤：

1. 对 ai 进行从小到大的排序；

2. 前一部分人的钱不足以支付平均数，因此他们每个人支付所有携带的钱；

3. 从总支付数中减去前一部分人支付的钱，得到剩余金额 S’，以及后一部分人的平均支付数 avg′。

4. 后一部分人携带的钱较多，他们可以支付多一些。这部分人又可以分为两类：

   • 相对富裕但仍然不足以支付 avg′ 的人，他们需要支付所有携带的钱；

   • 非常富裕的人，无论如何摊分，他们都有余额。

由于前面一部分人不足以支付 avg，因此后面足够支付 avg′ 的人不能只支付 avg。相反，他们应该尽可能地每个人支付相同的金额。

因为有人支付不足，总有人支付过多，由于是标准差（方差的平方根），因此每个人支付的金额差距越小越好。

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)个人的贡献,并加入ans
                break; // 跳出循环
            }
            ans += Math.pow(a[i]-avg,2); // 计算第i个人的贡献,并加入ans
            S -= a[i]; // 从剩余金额S中扣除第i个人的金额
        }

        System.out.printf("%.4f\n",Math.sqrt(ans/n)); // 输出标准差结果,保留4位小数
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

练习题

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解决思路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);//初始化0
        for(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);//最后复制最后九位数即是答案。
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15