《算法竞赛》详细介绍

  现在的蓝桥杯省赛，每次比赛有10题，其中5个填空，5个编程。
  每次比赛都有“送分题”，只需要几分钟就能做出来。特别是部分填空题，只需要填答案，不用提交代码，那么可以用包括编码在内的多种方法。编码一般比较慢，所以能不编码就不要编码，而是用推理和手算找到答案。这种不用编码的填空题称为“手算题”。
  竞赛的时间极为紧张，应选用最快的实现方式。
  下面给出4种小技巧：巧用编辑器、眼看手数、巧用Excel、巧用Python。

1. 巧用编辑器

（1）门牌制作

---

题目来源：2020年度C++ A组，试题A: 门牌制作
题目描述：1到2020的所有数字中，共有多少个2？

---

  这确实是个送分题，编码也很简单：判断每个数字中有几个2，然后把所有数字中2的个数加起来。编码大概5分钟。
  但是有更简单的做法：先编码打印出1~2020这2020个数字，然后粘贴到一个编辑器（word、codeblocks都行）中，选替换功能，用某个字符替换‘2’，共替换624次，这就是答案。用时1分钟。
  先用代码打印数字（用python写代码更短）：

#include<bits/stdc++.h>
using namespace std;
int main(){
  int k=0;
  for(int i=1;i<=2020;i++)
     cout<<i;
}

  打印出2020个数字：

  把数字贴回到codeblocks，替换了624次。

（2）2021年省赛新题"卡片"

今天（2021.4.18）省赛的A组第1题、B组第2题：

---

小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少？提示：建议使用计算机编程解决问题。

---

  和上面的例子差不多的做法。
  先估计可能拼出3000多个数。
  编个小程序打印出1~3500，然后全部贴到word里面，看1用了多少次，2用了多少次…
  最后发现，1~3181，用了2021个1，等等。所以答案是3181。
  后面用python再做一次。

2. 眼看手数

  有的填空题本身比较复杂，但是因为数据简单，此时用不着编码，直接用眼睛看，动手数。

（1）迷宫

---

题目来源：2017年度C++ A组，试题1: 迷宫
题目描述：给出一个迷宫，问迷宫内的人有多少能走出来。
迷宫如下：其中L表示向左走，R表示向右走，U表示向上走，D表示向下走。

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

---

  这道题是典型的DFS，编码至少10分钟。不过因为是个填空题，而且迷宫很简单，只有100个字符，可以直接数，从左往右数，从上往下数，约2分钟就能数完。数出来的结果见下面，红色字符上的人能走出来。

（2）七段码

---

题目来源：2020年度C++ A组，试题D: 七段码
题目描述：七段数码管，一共有7个发光二极管，问能表示多少种不同的字符，要求发光的二极管是相连的。

---

  题目要求发光的二极管是相连的，可以用DFS或并查集查找连通块，编码时间15分钟以上。不过，因为图形简单，直接手算也行，约3-5分钟。
  用字符表示数码管不太方便，改用数字：

  分7种情况：
  亮一个灯：有7种情况，1、2、3、4、5、6、7；
  亮两个灯：有12、13、23、24、25、…等等；
  亮三个灯：有123、124、125、134、136、234、257…等等；
  亮四个灯，这时不要直接数四个灯，情况与灭三个灯是等价的：灭123、灭124…等等；
  亮五个灯，与灭两个灯等价：灭12、灭13、灭14、…等等；
  亮六个灯，与灭一个灯等价，有7种情况；
  亮七个灯，有1种情况。
  对以上所有情况求和。

3. 巧用Excel

（1）数字计算

---

题目来源：2018年度C++ A组，试题1: 分数
题目描述：1/1 + 1/2 + 1/4 + 1/8 + 1/16 + …每项是前一项的一半，如果一共有20项,求这个和是多少，结果用分数表示出来。

---

  编码很简单，几分钟就好。也可以用Excel手算，时间差不多，而且不用思考。
  A列填分子，都是1；B列填分母，每行递增2倍，做法是，在B1填1，在B2填写“=B1*2”，然后按住B2往下拉到第20行，就填好了所有的分母。
  然后通分求分子分母。分母就是B20的524288，分子实际上就是“SUM(B1:B20)”，用鼠标选中这个区域，Excel自动算出1048575。

（2）日期问题

---

题目来源：2018年度C++ A组，试题2: 星期一
题目描述：整个20世纪(1901年1月1日至2000年12月31日之间)，一共有多少个星期一？

---

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

图(1) 日期做减法

  再用excel点2000年12月31日的属性，选星期，得“星期日”，说明答案就是5217。

图(2) 查看日期是星期几

4. 巧用Python

  Python处理数字非常简单，遇到这样的填空题，可以用Python。
  即使是参加C/C++、Java组比赛，也要学一些Python，以方便手算。
  Python的代码长度一般比C/C++、Java短很多，例如30行的C++代码，用Python写只需要20行。

（1）用Python算大数

---

题目来源：2018年度C++ A组，试题3: 乘积尾零
题目描述：给100个整数，问它们乘积的末尾有多少个零。

---

  遇到大数的问题，用Python处理是最简单的，可以直接硬算。
  不过，其实Python的大数也不是无限大的，下面的代码，如果一股脑先算出所有的100个数的乘积s，s实在太大了，也是会溢出的。所以乘一个数，就看乘积s后面有没有0，如果有0就除以10，这样s就比较小了。
  下面是“乘积尾零”问题的代码。

#输入放在一行中，不要分10行
num=[int(i) for i in input().split()] 
# input().split()读一行以空格分开的元素,然后用int()转为整数
s = 1
cnt = 0
for i in range(len(num)):   #连续乘，一边乘一边统计0的个数
    s *= num[i]             #乘一个数
    while s%10 == 0:        #末尾是零
       s /= 10              #除以10，把末尾零去掉
       cnt += 1 
print(cnt)

（2）用Python处理字符

---

题目来源：2019年度C++ A组，试题1: 平方和
题目描述：小明对数位中含有2、0、1、9 的数字很感兴趣，在1 到40 中这样的数包
括1、2、9、10 至32、39 和40，共28 个，他们的和是574，平方和是14362。
注意，平方和是指将每个数分别平方后求和。
请问，在1 到2019 中，所有这样的数的平方和是多少？

---

  用Python，不用任何算法，直接把数字看成字符来统计：

sum = 0
for i in range(1,2020):
    s = str(i)
    if '2' in s or '0' in s or '1' in s or '9' in s:
         sum += i*i
print(sum)

（3）

---

题目来源：2019年度C++ A组，试题2: 数列求值
题目描述：给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求
第20190324 项的最后4 位数字。

---

  下面是Python代码，直接算，非常简单：

a,b,c = 1,1,1
for i in range(4,20190325):
    y=(a+b+c)%10000
    a=b
    b=c
    c=y
print(y)

（3）2021年省赛新题

今天（2021.4.18）省赛的A组第1题、B组第2题：

---

小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少？提示：建议使用计算机编程解决问题。

---

用Python硬搞，简单直接！
先打印出20210个字符，然后每拼一个数字，就把对应的卡片去掉。
下面是3个代码：
（1）这是我写的，后来发现还是太麻烦了：

s =''                   #放20210个字符
for i in range(0,10):   #打印20210个字符
     for j in range(0,2021):
          s = str(i)+s

ans = 0                 #统计能拼的个数
for i in range(1,10000):     
     num = str(i)      #数字用字符表示
     len_card = len(num)   #这个数字有几位
     in_card = 1
     for j in range(len_card):
          if num[j] not in s:  #检查每个数字是不是在卡片里面
               in_card = 0       #这个数字拼不出来,结束
               print(ans)
               exit(0)
     if in_card == 1:    
          ans = ans+1
          for j in range(len_card):
               s=s.replace(num[j],"*",1)  #把用过的卡片去掉

答案 3181

（2）化药类2017林越洋的代码：

s=['0','1','2','3','4','5','6','7','8','9']*2021
for i in range(1,10000):
     a=list(str(i))
     try:
          for j in a:
               s.remove(j)
     except:
          print(i-1)
          break

(3)光电181陈韬的代码。因为数字1用得最多，统计到哪个数字的时候用了2021次个1，就好了。

s=""
for i in range(1,100000):
     s+=str(i)
     if s.count('1') == 2021:
          print (i)
          break