前言：

整体还是偏简单的，但有两题分别涉及到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这49个数字。法术一共持续7周，每天小明都要使用一张法术符，法术符不能重复使用。

每周，小明施展法术产生的能量为这周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 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法？

注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。

思路：

直接暴力要跑一万年，可以做下面两个的优化

1.找出不包含2和4的数字

2.整一个不重复元素集，两重循环，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
001001

110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按 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_爱吃花椒的刺猬酱的博客-CSDN博客_bfs迷宫问题 python

编程大题

特别数的和

题目：

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），

在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 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，如下图所示:

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大?如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注:根的深度是 1。

输入格式：

第一行包含一个整数 N。 第二行包含N个整数A1,A2,··· AN。

对于所有评测用例，1≤ N ≤100000，−100000≤ Ai ≤100000。

输出格式：

输出一个整数代表答案。

样例输入：

7 1 6 5 4 3 2 1

样例输出：

2

思路：

看了眼题目就逃了

蓝桥杯-完全二叉树的权值-python解法_晓宜的博客-CSDN博客

等差数列

题目：

问题描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式：
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A₁, A₂, · · · , AN。(注意 A₁ ∼ AN 并不一定是按等差数列中的顺序给出)
输出格式
输出一个整数表示答案。

样例输入：

5
2 6 4 10 20

样例输出：

10

思路：

先说一种网上很多人给的错误思路，但却能ac...

题目就是让我们找到最大的公差d是多少，给出的数字都是d的整数倍，那就找到最小的那个，这就是我们最大的公差。

比如 2，4，6，10，20

分别相差 2，2，4，10 那d=2

但我举两个反例

1. [2, 5, 9, 13, 17]

分别相差 [3，4，4，4]

这时候他的公差应该是1才对

到这里或许还能辩解，测试样例这么多公差为1肯定是少数情况，就算这么写也能拿到大部分分

那给出第二个反例

2. [2, 8, 17]

分别相差 [6, 9]，你还能强取公差为3吗？

所以通过这两个反例我们可以得到，公差应该是这些数字的最大公约数

python中求最大公约数的三种方法-Python学习网

代码：

## 错误逻辑 却能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 个整数 A1, A2, · · · , AN+M+1，小 明想知道在所有由这 N 个加号、M 个减号以及 N + M + 1 个整数凑出的合法的 后缀表达式中，结果最大的是哪一个?

请你输出这个最大的结果。
例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。

输入格式：

第一行包含两个整数 N 和 M。
第二行包含 N + M + 1 个整数 A1, A2, · · · , AN+M+1。

(对于所有评测用例，0≤ N,M ≤100000，−109 ≤ Ai ≤109。)

样例输入：

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

思路：

题目都没看明白...

蓝桥杯-灵能传输-python_晓宜的博客-CSDN博客_蓝桥杯灵能传输