【蓝桥杯】手算与思维题

手算与思维题

课程伊始，我们先要讲一下蓝桥杯相关的注意事项。

比赛流程

赛程：

  • 省赛
  • 决赛

省赛一等奖参加决赛

比赛时长 $4$ 小时

竞赛形式：

  • 个人赛，一人一机，全程机考
  • 答题过程中无法访问互联网
  • 不允许携带任何电子、纸质资料

参赛选手机器环境

  • X86 兼容机器，内存不小于 1G，硬盘不小于 60G 操作系统：Windows7、Windows8 或 Windows10。
  • C/C++ 开发环境：Dev-cpp 5.4.0 C/C++ API 帮助文档
  • Java 开发环境：JDK 1.8 Eclipse-java-2020-06 API 帮助文档
  • Python 环境：Python 3.8.6 IDLE（Python 自带编辑器）

题型

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

  • 程序设计 每道题目多个测试数据，$20% \sim 40%$ 是弱测试数据，其他是强测试数据。 题量大、时间紧张，难题往往不会做或来不及用高效算法编码，此时可以用暴力方法编程得 $20% \sim 40%$ 的分数。 程序设计题每题 $10% ~25%$ 分。

评分方式

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

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

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

知识点梳理

（1）思维题（杂题）：不需要算法和数据结构，只需要逻辑、推理的题目，难度可难可易。考察思维能力和编码能力，只能通过大量做题来提高。

（2）BFS 搜索和 DFS 搜索：也就是暴力搜索。这是非常基本的算法，是基础中的基础。

（3）动态规划：线性 DP，以及一些 DP 应用，例如状态压缩 DP、树形 DP 等。

（4）简单数学和简单数论。

（5）简单的字符串处理、输入输出，简单图论。

（6）基本算法：例如排序、排列、二分、倍增、差分、贪心。

（7）基本数据结构：队列、栈、链表、二叉树等。

技巧：手算

  • 应用场合：填空题
  • 手算的目的：减少做题时间，省下时间做编程题。

手段：

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

方法：

  • 巧用编辑器
  • 心算手数
  • 巧用 Excel
  • 巧用 Python

例题

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

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

  • 先编码连续打印出 $1$ $\sim$ $2020$ 这 $2020$ 个数字
  • 然后粘贴到任何一个编辑器中
  • 选查询或替换功能，查找或替换字符 “$2$”，共 $624$ 次，就是答案。

简单直接，不用思考

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

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

1
2
3
4
5
6
7
8
9
10
UDDLUULRUL
   UURLLLRRRU 
   RRUURLDLRD 
   RUDDDDUUUU 
   URUDLLRRUU 
   DURLRLDLRL 
   ULLURLLRDU 
   RDLULLRDDD 
   UUDDUDUDLL 
   ULRDLUURRR
  • 正解：DFS 搜索，编码 10 分钟。
  • 技巧：直接用手画图标记 3-5 分钟。

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

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

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

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

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

也可以直接利用 Excel“单元格格式”对话框得出 $2000$ 年 $12$ 月 $31$ 日刚好是星期天，从星期二至星期天之间没有星期一。

巧用 Python

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

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

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

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

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

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

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

1
2
3
4
5
6
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)

相对应的使用 C++同样可以完成，但是编码复杂：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream> 
using namespace std; 
int res; //先判断润年 
bool is_r(int n){ 
    if((n % 4 == 0 && n % 100 != 0) || n % 400 == 0) return true; return false; 
} 
int main(){ 
    for(int i = 1901;i <= 2000;i ++) 
        if(is_r(i)) res += 366; 
    else res += 365; 
    int x = res / 7; 
    cout << x << endl;
    return 0; 
}

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

【问题描述】 给出 $100$ 个整数（这里省略题目给的 $100$ 个数），问它们乘积的末尾有多少个零。

最简单题解：

  • 直接连乘：几千位的大数
  • 然后统计末尾的 $0$

图片描述

但是 C++ 装不下这么大的数字，所以要进行处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main(){
    int cnt2=0,cnt5=0;
    for (int i=1;i<=10;i++) {
        for (int j=1;j<=10;j++) { 
            int x; 
            cin>>x;
            while (x%2==0) cnt2++,x/=2; 
            while (x%5==0) cnt5++,x/=5; 
        } 
    } 
    cout<<min(cnt2,cnt5)<<'\n';
    return 0; 
}

发现编码时间变长了，如果填空题且 Java 学的好一点的，可以直接 Python 编程出结果。

思维题

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

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

【题目描述】

现在有 $n$ 个人出去吃饭，他们总共消费了 $S$ 元。其中第 $i$ 个人带了 $a_i$元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 $S$ 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的”偏差有多大”。形式化地说，设第 $i$ 个人付的钱为 $b_i$ 元，那么标准差为 :

$\sqrt{\frac{1}{n}\Sigma_{i=1}^{n}(b_{i}-\frac{1}{n}\Sigma_{i=1}^{n}b_{i})^{2}}$

解决思路：

如果每个人携带的钱足够多，每个人平均支付相同的金额，即 $b_i = \frac{S}{n} = \text{avg}$，那么标准差 $X$ 为 $0$。

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

（1）第 $i$ 个人携带的钱不足以达到平均数 $\text{avg}$，那么他只能支付他所携带的全部钱 $a_i$。

（2）第 $i$ 个人携带的钱超过平均数 $\text{avg}$，那么他可以支付多一些。

解决步骤：

（1）对 $a_i$ 进行从小到大的排序；

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

（3）从总支付数中减去前一部分人支付的钱，得到剩余金额 $S’$，以及后一部分人的平均支付数 $\text{avg}’$。

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

  • （i）相对富裕但仍然不足以支付 $\text{avg}’$ 的人，他们需要支付所有携带的钱；
  • （ii）非常富裕的人，无论如何摊分，他们都有余额。

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

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

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
#include <bits/stdc++.h>
using namespace std;
const int M = 5e5;
long long a[M];
int main(){
    int n;  long long s;
    scanf("%d %lld",&n,&s);

    for(int i=1;i<=n;i++)  scanf("%lld",&a[i]);

    sort(a+1,a+n+1);       //排序，从小到大

    double avg = 1.0*s/n;  //平均值
    double sum = 0.0;

    for(int i=1;i<=n;i++){
        if(a[i]*(n+1-i) < s){
//需要把钱全拿出的人：
//（1）钱不够平均数的，（2）钱够平均数，但也不是很多的
            sum += (a[i]-avg)*(a[i]-avg);
            s -= a[i];            //更新剩余钱数
        }
        else{      
//不用把钱全拿出的人：非常有钱，不管怎么平均都够
            double cur_avg = 1.0*s/(n+1-i);    
//更新平均出钱数
            sum += (cur_avg-avg)*(cur_avg-avg)*(n+1-i);
            break;
        }
    }
    printf("%.4lf",sqrt(sum/n));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from math import *
n, s = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
avg = s/n
sum = 0
for i in range(n):
     if a[i]*(n-i) < s:
          sum += pow(a[i]-avg,2)
          s -= a[i]
     else:
          cur_avg = s/(n-i);      #更新平均出钱数
          sum += pow(cur_avg-avg,2)*(n-i)
          break
print("{:.4f}".format(sqrt(sum/(n))))
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
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;
        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]) {
                ans += (n-i)*Math.pow((double)S/(n-i)-avg,2);
                break;
            }
            ans += Math.pow(a[i]-avg,2);
            S -= a[i];
        }
        System.out.printf("%.4f\n",Math.sqrt(ans/n));
    }
}
≡