【蓝桥杯】手算与思维题

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

比赛流程

赛程：

省赛
决赛

省赛一等奖参加决赛

比赛时长 $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$ 表示向下走。

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 行可以输出某个日期是星期几。

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++同样可以完成，但是编码复杂：

#include  
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 [4. 乘积尾零 2018 年第九届蓝桥杯省赛](https://www.lanqiao.cn/problems/612/learning/)

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

最简单题解：

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

- 然后统计末尾的 $0$

![图片描述](/images/DSA-MentalMathAndBrainTeasers/236f300ccb9673d4fc3b0c7790de774a-0.png)

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

```cpp
#include 
using namespace std;
int main(){
    int cnt2=0,cnt5=0;
    for (int i=1;i>x;
            while (x%2==0) cnt2++,x/=2; 
            while (x%5==0) cnt5++,x/=5; 
        } 
    } 
    cout发现编码时间变长了，如果填空题且 Java 学的好一点的，可以直接 Python 编程出结果。

## 思维题

- 不需要涉及某种算法的题目。

- 只要学过编程语言，就能够解答。

- 主要考核学生的思维、逻辑和编码能力，强调脑筋急转弯的解决方式。

- 这类题目包括模拟题、构造题、思维题以及找规律题，统称为“思维题（杂题）”。

- 每年蓝桥杯都会设置这类题目，而且可能有多道，是考试中的重要得分点。

- 杂题涵盖了各种难度，有些可能相对简单，而另一些可能相对较难。

[5. 付账问题 2018 年第九届蓝桥杯省赛，lanqiaoOJ 题号 174](https://www.lanqiao.cn/problems/174/learning/)

【题目描述】

现在有 $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}$。相反，他们应该尽可能地每个人支付相同的金额。

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

```cpp
#include 
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

[← 下一篇 【蓝桥杯】递推法与递归法](/posts/dsa-recurrenceandrecursive/)

【Hexo】问题解决方案（该文章已随 Hexo 站点一并归档，不再提供）