2019年第十届蓝桥杯python组省赛
前言：
总体来说比较简单。不过其中包含两道题目涉及到了BFS算法以及完全二叉树结构的内容，这些领域是我之前未学过的内容。复习时再来补充这部分内容吧。近期计划复习期末考试的相关内容。
目录
填空题
平方和
数列求值
最大降雨量
年号字串
数的分解
迷宫
编程大题
特别数的和
完全二叉树的权值
等差数列
后缀表达式
灵能传输
填空题
平方和
题目：
小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到40 中这样的数包括 1、2、9、10 至 32、39 和 40，共28 个，他们的和是574，平方和是 14362。
注意，平方和是指将每个数分别平方后求和。
请问，在 1 到2019 中，所有这样的数的平方和是多少？
思路：
暴力枚举就好了
代码：
def panduan(num):
num=str(num)
for i in num:
if i=='2' or i=='0' or i=='1' or i=='9':
return True
return False
res=0
for i in range(1,2020):
if panduan(i):
res += i**2
print(res)答案：2658417853
数列求值
题目：
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。
思路：
没有独特的想法，
以提高运行速度为目标，
我们只需要关注最后四位数字即可（取余运算）
代码：
## 取余跑快点
t1,t2,t3=1,1,1
for i in range(20190321):
res=(t1+t2+t3)%10000
t1=t2
t2=t3
t3=res
#print(i)
print(res)答案：4659
最大降雨量
题目：
由于沙之国长期干旱,法师小明决定施展一种独特法术以求降雨。
这种法术需要耗费他手中的49张不同面值的法术符,这些符上分别写着从1到49的不同数字。
整个过程持续7周,每周小明都会消耗一张独特的法术符,并且不能重复使用同一枚符。
每周结束时,小明施展法术所产生能量等于该周7张法术符上数字的中位数值。
经过完满施展后,降雨量将由这7周能量数值的中位数决定。
鉴于连续干旱多时,小明希望能够使此次求雨获得最大的降雨量,请问最大值是多少？
思路：
也就是49个值，我们最后只需要中位数的中位数的值最大
画图：
圆圈位置即为最终结果。我们的目标是使该值最大化；只要满足条件即可（√处的数据必须大于⚪处的数据，并且这是因为中位数的原因）。
答案：49-15=34
年号字串
题目：
小明将字母 A 设为数字 1，并依次类推使 B 到达数字 2的位置；以此延续至字母 Z 被分配给数字26。
在数值超过等于27的情况下，则采用两位或更多位数的组合形式进行编码；具体而言：
AA 被定义为第27个位置，
AB 则对应第28个，
AZ 则对应第52个，
而 LQ 则代表第329个位置。
那么，请问数字2019对应的字符串是什么？
思路：
思路一.用excel，横向拉满1~2019，对应结果就是答案（蓝桥杯比赛时可以使用excel
思路二：
2019%26=17
所以最后一个值是Q
2019//26=77
如果最后值再（1,26]之间则为两个字母，大于26代表不止两个
77%26=25
所以倒数第二个值是Y
77//26=2
倒数第三个值是B
答案：BYQ
数的分解
题目：
将数字2019拆分为三个互不相同的正整数之和，并且每一个正整数都不含有数字2或4的不同组合共有多少种？需要注意的是，在计算过程中，默认交换三个整数的顺序视为同一种情况。
思路：
直接暴力运行时间极长
可以采取以下两种优化策略
第一种策略是筛选出不含数字2和4的数值集合
第二种策略是构建一个不重复元素的集合
并采用双重循环结构
其中i从1取值到2019除以3的结果向下取整
j从i+1开始一直到2019减去(i+1)的位置为止
k则等于2019减去i与j的总和
代码：
nums=[]
for i in range(1,2020):
t1=str(i)
if ('2' not in t1) and ('4' not in t1):
nums.append(int(t1))
res=set()
for i in range(1,674):
for j in range(i+1,2019-i):
k=2019-i-j
if (i in nums) and (j in nums) and (k in nums):
if i!=j and i!=k and j!=k:
if i+j+k==2019:
t2=[i,j,k]
t2.sort()
res.add(tuple(t2))
#print(i)
print(len(res))答案：40785
迷宫
题目：
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。
010000
000100
001001110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫，一共 10 步。
其中 D、U、L、R 分别表示向下、向上、向左、向右走。
.
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 D < L < R < U。
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000思路：
还未掌握BFS算法, 因考试未通过而打算日后弥补.
蓝桥杯 python 走迷宫 BFS_爱吃花椒的刺猬酱的博客-博客_bfs迷宫问题 python
编程大题
特别数的和
题目：
小明对各位包含有数字 2、0、1、9 的数值表现特别兴趣（不考虑前导零）。这些数涵盖范围内的数值包括：1至40中的各位包含有数字2,0,1,9的数值。共计有 28 个这样的数值。那么，在给定任意正整数n的情况下，请问这些符合条件的数值之和是多少？
思路：
签到dd！
代码：
def have(num):
num=str(num)
for i in num:
if i=='2' or i=='0' or i=='1' or i=='9':
return True
return False
n=int(input())
res=0
for num in range(1,n+1):
if have(num):
res += num
print(res)完全二叉树的权值
题目：
考虑一个具有 N 个节点的完全二叉树，在该树中每个节点都具有一个权重值。这些权重值按照自上而下的顺序排列为 A1, A2, …, AN。
如图所示：
该序列按照从顶到底、依次向右的方式进行排列。
现在小明希望将具有相同深度的所有节点的权值相加。他想了解哪个深度对应的总权值最大？如果存在多个达到最大总权值的情况，请输出最小的那个深度。
样例输入：
7 1 6 5 4 3 2 1
样例输出：
2
思路：
稍作粗略浏览后便感到有些沮丧或失望。
文章标题：蓝桥杯-完全二叉树的权值-python解法
文章来源：晓宜的博客-
等差数列
题目：
问题陈述
老师为小明布置了一个涉及等差数列求和的问题。
由于马虎，小明遗漏了部分数列的信息。
现在我们得到了这 N 个整数。
小明希望确定包含这 N 个整数的最短等差数列共有多少项。输入格式：
输入的第一行包含一个整数 N。
第二行包含 N 个整数组成的序列 A₁, A₂, · · · , AN。（注意这些整数组不一定是按等差顺序给出）
输出格式：
输出一个表示答案的整数值。
样例输入：
5
2 6 4 10 20
样例输出：
10
思路：
另一种常见的错误思路是……但通过测试却能通过。这种思路的核心在于先假设某种情况成立，并试图寻找满足条件的最大公差d。然而，在实际操作中这种方法可能会因为某些特殊情况而失效或者无法得到正确的结果。
我们的目标是确定最大的公差d值。
所有给出的数字都是d的整数倍。
因此我们只需要找到这些数字中的最小值即可确定d的最大值。
例如序列：2,4,6,10,20
它们之间的间距依次是2、2、4和10，则最大公约数为2。
这时正确的最大公约数应为1。
第一个反例：[2,5,9,13,17]
第二个反例是：[2,,8,,,,9,,,]
在这两种情况下我们的方法均有效。
所以通过这两个反例可以看出这种方法虽然简单却并不总是适用。
代码：
## 错误逻辑 却能ac
## 给出错误代码是希望大家通过调用能看到结果是错误的
n=int(input())
nums=list(map(int,input().split()))
nums.sort()
mins=1000000
for i in range(1,len(nums)):
mins=min(mins,nums[i]-nums[i-1])
if mins==0:
print(len(nums))
else:
print((nums[-1]-nums[0])//mins+1) ## 正确做法
def find(nums):
mx, mn = max(nums), min(nums)
while mx % mn != 0:
tmp = mx % mn
mx, mn = mn, tmp
return mn
n=int(input())
nums=list(map(int,input().split()))
nums.sort()
d=set()
for i in range(1,len(nums)):
d.add(nums[i]-nums[i-1])
d=list(d)
if min(d)==0:
print(len(nums))
d=find(d)
print(int((nums[-1]-nums[0])/d + 1))后缀表达式
题目
假设我们有N个加法算子、M个减法算子以及N+M+1个整数组成一个序列A₁,A₂,…,A_{N+M+1}。他关心的是这些运算符与数组构成的所有合法后缀表达式中能够取得的最大值是多少？
请输出这个最大值的结果。
例如采用序列"1","2","3"并执行运算"-"得到的结果为4（具体计算过程为先计算"2"+"3"得到5再用5减去"-"操作得到结果4）。
输入格式：
第一行给出两个整数N和M。
第二行给出包含N+M+1个整数A₁,A₂,…,A_{N+M+1}（具体数值范围见约束条件）。
对于所有测试数据中的案例我们有0≤N,M≤1e5且-1e9≤A_i≤1e9（i=₁,…,N+M+₁）。
样例输入：
1 1
1 2 3
样例输出：
4
思路：
一开始没看懂题目，加号优先给大的，给完了减号再给小的。最后才30分。
上网检索后才发现可以添加括号,括号可以使减号加号进行转换
例：
3 1
[-4, -3, 1, 2, 5]
正确做法：5-((-4)+(-3))+2+1=15
然后就是找规律
1.没有减号
那就全部数相加
2.有减号
2.1 没有负数
例：2 2
[1, 2, 3, 4, 5]
(2+3+4)-(1-5)=13
如果是 3 1
则：(2+3+4)+(5-1)=13
如果是 0 3
则： 5-（1-4-3-2）=13
得到规律：（max-min）+其他数
有负数的情况下也可得到上述规律
等价于 （max-min）+ abs（x1）+ abs（x2）+ ....
代码：
## 先排序别忘了
n,m=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
if m==0:
print(sum(nums))
else:
res=nums[-1]-nums[0]
for i in range(1,len(nums)-1):
res += abs(nums[i])
print(res)灵能传输
在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在 游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对 一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的 刺蛇飞龙等低血量单位。
你控制着 n 名高阶圣堂武士，方便起见标为 1, 2, · · · , n。每名高阶圣堂武士 需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少(ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这 名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态)。现在系统赋予了 你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i ∈ [2, n − 1]，若 ai ≥ 0 则其两旁的高阶圣堂武士，也就是 i − 1、i + 1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能;若 ai < 0 则其两旁的高阶圣堂武士， 也就是 i − 1, i + 1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。形 式化来讲就是 ai−1+ = ai, ai+1+ = ai, ai− = 2ai。
灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂
武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为
maxn |ai|，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武 i=1
士的不稳定度最小。
输入格式：
本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。 接下来依次输入每一组询问。
每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。 接下来一行包含n个数a1,a2,··· ,an。(对于所有评测用例，T ≤ 3，3 ≤ n ≤ 300000，|ai| ≤ 109。)
输出格式：
输出 T 行。每行一个整数依次表示每组询问的答案
样例输入：
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
样例输出：
3
0
3
思路：
主题都没看明白...