蓝桥杯|蓝桥杯python（题目思路即解答（笔记，持续更新）） python|算法|蓝桥杯

这篇文章是为蓝桥杯做准备时顺便做的笔记，用来讨论即参考用的，如有错误欢迎指正，有更好的方法也可以提出来一起讨论，谢谢各位大佬们orz
因为本人不是VIP，只能刷蓝桥杯里面的普通题，还请见谅orz
注：代码中的input别尚自加东西进去，会报错。别问，问就是血淋淋的教训，改了半个小时的代码QAQ
基础练习 A+B问题

content = input() str_list = content.split(' ') int1 = int(str_list[0]) int2 = int(str_list[1]) result = int1 + int2 print(result)

数列排序
【蓝桥杯|蓝桥杯python（题目思路即解答（笔记，持续更新））】这道题我自己写了一个快速排序，也是给自己做练习用的，可以直接用python自带的排序函数
python自带函数

n = int(input()) arr = list(map(int,input().split())) arr = sorted(arr) for i in range(n): print(arr[i],end=' ')

快速排序

n = int(input()) arr = list(map(int,input().split())) def partition(arr,low,high): i = low j = high if low < high: key = arr[low] while i < j: while arr[j] >= key and j != i:#向前寻找，找寻比key小的数 j-=1 arr[i],arr[j] = arr[j],arr[i]#交换位置 while arr[i] < key and i != j:#向后寻找，找寻比key大的数 i+=1 arr[j],arr[i] = arr[i],arr[j]#交换位置 else: partition(arr,low,i-1) partition(arr,i+1,high) partition(arr,0,n-1) for i in range(n): print(arr[i],end=' ')

十六进制转八进制

n = int(input()) arr = [] j = 0 for i in range(n): arr.append(input()) for i in arr: print(oct(int(i,16)).split('o')[-1])

十六进制转十进制

n = input() print(int(n,16))

十进制转十六进制
这道题里面的输出要注意，他要求输出的字母是大写，所以可以用upper函数转过来

n = int(input()) a = hex(n).split('x')[-1] print(a.upper())

特殊回文数
代码中的continue是出于习惯加进去的，听说在循环里能加快运行速度，但实际本人并没有测试过

n = int(input()) for i in range(10000,1000000): istr = str(i) if istr[:] == istr[::-1]: b = [int(j) for j in istr] if sum(b) == n: print(i) else: continue else: continue

回文数
回文数的特点就是正向读和反向读是一样的，所以可以直接判定字符串正向和反向是否相同即可

for i in range(1000,10000): istr = str(i) if istr[:] == istr[::-1]: print(i)

特殊的数字

def ok(a):#用于映射 return a**3 for i in range(100,1000): istr = str(i) iint = [int(j) for j in istr] iint = list(map(ok,iint)) if sum(iint) == i: print(i)

杨辉三角形
方法一

n = int(input()) k = []#用来存储杨辉三角形的元素 for i in range(1,n+1): if i == 1: k.append(1) print(1) else: for j in range(1,i+1): if j == 1:#第一列都是1 print(1,end=' ') k.append(1) elif j == i:#每行的最后一列也是1 print(1) k.append(1) else: #从杨辉三角形中找规律，可以发现除第一列和最后一列的元素，其它的都是其上一行正上方的元素加左上角的元素，所以找到其在列表k中对应的位置即可 num = int(i*(i+1)/2) - i + j k.append(k[num-i]+k[num-i-1]) print(k[num-i]+k[num-i-1],end=' ')

方法二 ??第一个方法就直接推规律即可，第二个方案是按照杨辉三角的规律公式来的，每个元素的值与其行列的关系如下： a i j = C i ? 1 j ? 1 a_{ij}=C_{i-1}^{j-1} aij?=Ci?1j?1?
其中 i i i表示第 i i i行， j j j表示第 i i i行内从左到右第 j j j个
C C C为排列组合中的组合，高中知识，就不多解释了

n = int(input()) def C(n,m):#组合函数 M = 1 N = 1 for i in range(1,m+1): M*=i N*=(n-i+1) return int(N/M) for i in range(1,n+1): for j in range(i): if j == i-1: print(C(i-1,j)) else: print(C(i-1,j),end=' ')

查找整数

n = int(input()) iint = list(map(int,input().split())) m = int(input()) j = 0 for i in range(len(iint)): if m == iint[i]: print(i+1) j+=1 break if j == 0: print(-1)

数列特征

n = int(input()) iint = list(map(int,input().split())) print(max(iint)) print(min(iint)) print(sum(iint))

字母图形

num = list(map(int,input().split())) n = num[0] m = num[1] d = [chr(i) for i in range(65,91)]#先获得字母表的字母 for i in range(n): for j in range(m): k = abs(i - j)#找规律，发现每个字母的位置对应其行数减去其列数的绝对值 print(d[k],end = '') print()

01字串
这个代码并不泛用，只是单纯为了解决这道题而已，如果要求01编码长度大于5就凉了〒▽〒

for i in range(32): a = bin(i).split('b')[-1] n = 5-len(a) b = ['0']*n result = ''.join(b) + a print(result)

闰年判断

year = int(input()) if year % 4 == 0 and year % 100 != 0 or year % 400 == 0:#按要求判断 print('yes') else: print('no')

Fibonacci数列
网上找的方法，自己的理解是相加的话先求余和后求余一样，先求余可以防止大数字出现，加快计算速度
但本人觉得计算速度应该不会差太多，有大佬解释一下吗orz 为什么不能先求和后求余呢

n = int(input()) f1 = 1 f2 = 1 if n > 2: for i in range(3,n+1): f3 = (f1 + f2) % 10007 f1 = f2 f2 = f3 print(f3) else: print(f1)

圆的面积
没什么说的，要求到小数点后7位，所以pi精确度要高一些，输出用正则即可

r = int(input()) PI=3.14159265358979323 print('%.7f'%(PI*r**2))

序列求和
等差序列的前n项和，直接套公式

n = int(input()) snum = (1+n)*n/2 print(int(snum))

算法训练印章
??可以把这道题看成盒子放球的问题，将n种印章看成n个盒子，然后购买m张印章看成拥有m个相同的球。所以我们只要求n个盒子里都有球的概率即可
这里采用逆向思维（直接算过于复杂），计算至少有一个盒子没有球的概率
可以得到下面公式：
某一个盒子为空：
P { A i } = ( 1 ? 1 n ) m P\left \{ A_{i} \right \}=\left ( 1-\frac{1}{n}\right)^{m} P{Ai?}=(1?n1?)m
同理，某两个盒子为空：
P { A i A j } = ( 1 ? 2 n ) m P\left \{ A_{i}A_{j} \right \}=\left ( 1-\frac{2}{n}\right)^{m} P{Ai?Aj?}=(1?n2?)m
以此类推，有
P { ? i = 1 n ? 1 A i } = ( 1 ? n ? 1 n ) m P\left \{ \bigcap_{i=1}^{n-1} A_{i} \right \}=\left ( 1-\frac{n-1}{n}\right)^{m} P{i=1?n?1?Ai?}=(1?nn?1?)m
由n个相容事件的概率公式可得
P { B } = C n 1 ( 1 ? 1 n ) m ? C n 2 ( 1 ? 2 n ) m + ? + ( ? 1 ) n ? 1 C n n ? 1 ( 1 ? n ? 1 n ) m P\left \{ B \right \}=C_{n}^{1}\left ( 1-\frac{1}{n} \right )^{m}-C_{n}^{2}\left ( 1-\frac{2}{n} \right )^{m}+\cdots+\left ( -1\right )^{n-1}C_{n}^{n-1}\left ( 1-\frac{n-1}{n} \right )^{m} P{B}=Cn1?(1?n1?)m?Cn2?(1?n2?)m+?+(?1)n?1Cnn?1?(1?nn?1?)m
所以所有盒子里都装有球的概率为
P { C } = 1 ? P { B } P\left \{ C \right \}=1-P\left \{ B \right \} P{C}=1?P{B}
借鉴文章：
蓝桥杯算法训练-印章

[1]蔣茂森.n个相容事件和的概率公式及其应用[J].数学通报,1964(11):39-40.

num = list(map(int,input().split())) n,m = num[0],num[1] def C(n,m):#组合函数 M = 1 N = 1 for i in range(1,m+1): M*=i N*=(n-i+1) return N/M if n > m:#当买的次数比印章的种类少时，肯定不可能买全 print('%.4f'%0) else:#按公式计算 empty = [(-1)**(i+2)*C(n,i+1)*(1-(i+1)/n)**m for i in range(n-1)] print('%.4f'%(1 - sum(empty)))

拿金币
??这是典型的DP问题，它要求我们计算到右下角时所能获得的最大金币数，限制是只能往右或者往下移动。
??思路也比较简单，我们计算所到达的每个地方所能获得的最大金币数即可
??首先考虑它从起点到终点需要多少步，通过规律可以发现n阶矩阵起点到终点的步数为(n-1)*2,即循环次数。然后考虑它每个步数可能到达的位置，这样就不用算出所有位置的最大金币。在之后就更新矩阵，将得到的最大金币数更新在矩阵对应的位置即可，直到更新到最后一行一列即为最终答案。

n = int(input()) matrix = [] for i in range(n): matrix.append(list(map(int, input().split()))) for i in range(1,(n - 1) * 2 + 1):#n阶矩阵走到终点的步数为(n-1)*2 if i < n:#如果i=n，则起点可以在第i-n+2行，至多在第n行 start = i - n + 1 end = n for j in range(start,end): k = i - j#判断现在位于第几列 if j == 0:#如果在第一行，则表示上个位置是在其左边 matrix[j][k] = matrix[j][k-1] + matrix[j][k] elif k == 0:#如果在第一列，则表示上个位置是在其上方 matrix[j][k] = matrix[j-1][k] + matrix[j][k] else:#如果都不是，则表示上个位置可以在其上方或者在左边，计算到达这个点的最大金币 matrix[j][k] = max(matrix[j][k-1],matrix[j-1][k]) + matrix[j][k] print(matrix[-1][-1])

数字游戏
??首先要做这道题，要先知道这道题和杨辉三角的关系，以题目给的例题的例：输入4，16，输出3 1 2 4。因为我们可以知道杨辉三角第四行的元素为(1,3,3,1)，其值关系有： 3 ? 1 + 1 ? 3 + 2 ? 3 + 4 ? 1 = 16 3*1+1*3+2*3+4*1=16 3?1+1?3+2?3+4?1=16，可以看到，杨辉三角第n行的元素与输出的值对应相乘后相加，得到的结果便是数字游戏最后的数字。
??所以我们第一步便是先求得杨辉三角第n行的元素，其方法在上面的杨辉三角形方法二中有提到，稍加修改即可
??得到杨辉三角第n行的元素后，我们便要找到一组输出值，使得满足上述所说的要求。这里直接采用深度优先搜索（DFS）来实现
??由于本人DFS学得也不精，怕讲出来误导别人，而且网上也没找到讲得比较清楚的，这里便不多做说明，有兴趣的可以去找一下了解一下。下面附上代码：

def C(n,m):#组合函数 M = 1 N = 1 for i in range(1,m+1): M*=i N*=(n-i+1) return int(N/M) def YH_triangle(n):#杨辉三角最后一行判定 l = [] if n == 1: l.append(1) else: for i in range(n): l.append(C(n-1,i)) return l def dfs(num=0,t_sum=0):#dfs算法，参数依次为搜到第几个、目前总和 global flag if flag == 1:#判断条件，如果flag=1则代表找到答案 return if t_sum > s:#如果计算值大于目标值，则可以提前结束这个命令 return if num == n: if t_sum == s:#找到目标 flag = 1 for j in l_s: print(j,end=' ') else: returnfor i in range(1,n+1): if u[i] == 0:#记录进栈情况，栈点有元素的以1标记 u[i] = 1 l_s.append(i) dfs(num+1,t_sum+l[num]*i)#迭代 u[i] = 0#进栈元素不符合，重置为0，该元素退栈 l_s.pop() if __name__ == '__main__': n,s = map(int,input().split()) if n == 1: print(s) else: l = YH_triangle(n) u = [0] * s l_s = [] flag = 0 dfs()

思路出处：
蓝桥杯算法训练数字游戏Python实现（dfs 回溯）
无聊的逗
??这道题首先你得先获得题目给定元素的所有组合，即它的数列子集；然后对所有的数列子集进行判断，判断是否满足题目要求，即将子集拆成两部分，使得这两部分的和相等，最后选出满足要求且和最大的子集，返回题目所要结果。
代码如下，简单的讲解一下代码：
??首先是创建一个获取子集的函数subsets，然后将获取的所有子集一次塞进函数half_max中，判定哪些子集满足要求且返回满足要求的等同子集和。
??在half_max函数中，首先有判定列表和是否为偶数，因为前面说到满足要求的子集可以分成两个互不相交且和相等的部分，所以任意一部分的和乘以2即为这个子集的总和，为偶数
??然后在讲一下里面L[j]=L[j] or L[j - num]所包含的整个二重循环，该循环的作用是获取一个子集中任意n(0<=n<=元素个数)个元素相加可能出现的值，得到一个长度为子集和一半+1的布尔列表，举个例子：有一个子集为(1,3,4)，则有一个列表长度为(1+3+4)/2+1=5，通过该循环可以得到该布尔列表如下：[True, True, False, True, True]，该列表从左到右表示0、1、2、3、4，对应位置为True的，表示子集中任意n(0<=n<=元素个数)个元素相加能够出现这个数值，比如子集中三个元素都不选，则没有元素相加，默认为0，所以0对应位置为True；1同样道理，只选择元素1即可；而4对应的布尔列表True可以是1+3也可以是4本身。该列表用于判断目标数值是否能被子集中的元素相加所得到，不能则返回False。

n = int(input()) l = list(map(int,input().split())) def subsets(l): res = [[]] for i in l: res = res + [[i] + num for num in res]#获取列表l中元素的所有组合 return res def half_max(nums):#传入一种组合的列表 target = sum(nums)#获取列表总和 if target % 2:#判断target是否为偶数，如果不是则代表则个组合不可能 return False,target target = target // 2#这行代码等同于target=int(target/2) if max(nums) > target:#列表元素不可能大于target return False,target L = [True] + [False]*target#初始化列表 for num in nums: for j in range(target,num-1,-1):#获取该列表元素的所有可能出现的和 L[j] = L[j] or L[j - num] return L[target],target#L[target]返回布尔值，代表这组元素组合是否符合要求max_result = 0#初始化最大长度 nums = subsets(l)#求出组合 nums.pop(0)#删除第一个空子集for num in nums:#将所有组合都遍历一遍 flag,target = half_max(num) if flag and target>max_result:#选择符合要求且数值最大的结果 max_result = target print(max_result)

思路出处：
蓝桥杯无聊的逗 Python题解
背包问题应用，LeetCode 416. 分割等和子集（Python实现）
礼物
??这道题本人是真的无能为力了，不知道是蓝桥杯练习系统没考虑语言不同所带来的运行时间不同还是，我采用了同样的方法，在c++那就通过了，但python时间就一直时间超出，下面就讲解一下思路，看看有没有大佬能够优化一下
??这道题我采用了二分法来解决，简单的解释一下二分法：
??有一个猜数字游戏，给你一个0-10的数，让你猜是哪一个，你每次猜一个数，我会根据情况给你三个回答：“大了”，“小了”，“正确”。在排除运气等成分的情况，怎样才能让你快速锁定正确答案呢？
??因为我们不知道是哪个数字，所以我们往往会先从中间下手，也就是（0+10）/2=5，如果这个时候的回答是大了（小了），我们便会往这个数字的下半（上半）搜索，而这个时候问题就变成了“给你一个0-4（6-10）的数，让你…”，而这时我们只需要重复上面的步骤，在最终搜索区间会缩小成一个数，而这个数便是我们的最终答案。
??而这便是二分法的做法，他的每一次搜索都能帮我们排除掉一半的区间，从而加快我们的搜索速度，它的时间复杂度为 O ( log ? 2 n ) O\left (\log_{2}{n} \right ) O(log2?n)
??而在这道题了，我们可以把问题变成，先确认 ( 1 + n ) / 2 \left ( 1+n \right ) /2 (1+n)/2是否满足要求，如果是，则确认 ( ( 1 + n ) / 2 + n ) / 2 \left (\left ( 1+n \right ) /2 +n\right ) /2 ((1+n)/2+n)/2是否满足要求，否则确认 ( 1 + ( 1 + n ) / 2 ) / 2 \left (1+\left ( 1+n \right ) /2 \right ) /2 (1+(1+n)/2)/2是否满足要求，依此类推，直到最终前后两个数相等，输出该数的两倍即可（题目要求）。
??在python中，类似append、切片、max(min)的时间复杂度较高，所以一般在循环中要避免出现这些，所以在计算前缀和之前，我先对列表初始化，然后采用赋值的方式来修改列表；而采用前缀和，也是为了避免使用切片.
前缀和：arr[i]表示1-i个石头的重量和
注：这个方法如果采用C++实行，则能满足，用python不行，穷途末路了orz

N,S = map(int,input().split()) L = list(map(int,input().split())) arr = [0] * (N+1)#初始化列表 for i in range(1,len(L)): arr[i] = arr[i-1] + L[i]#前缀和 def check(mid):#查找是否符合条件，返回True和False for i in range(mid,N-mid+1): if arr[i] - arr[i-mid] <= S and arr[i+mid] - arr[i] <= S: return True return False l,r = 1,N while l < r: mid = (l+r+1)>>1#等价于(l+r+1)/2,k>>n等价于k/(2**n)，如果结果小于1，则返回0； if check(mid):#满足条件，更新l=mid l = mid else:#否则更新r r = mid - 1 print(2*l)

跳马
??这道题我采用深搜（dfs）来解决，直接用dfs将所有满足条件的路线找到，然后直接返回最小步数即可。
??因为每次棋子往八个方向走动，且下一次走动依旧有八个方向，为了简便代码，直接采用一个二维数组来更新方向，这样就不用将八个方向对应的函数写一遍。
??剩余部分在注释里有，不懂的或有更好思路的也可以在评论里说一下
??代码感觉还有优化空间，感觉写的啰嗦了，但因为时间关系就不完善了orz

position = list(map(int,input().split())) d = [[2,1],[1,2],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]]#用二维数组储存方向 l = [[0 for i in range(10)] for j in range(10)] l[position[0]][position[1]] = 1#初始位置标记为1 l[position[2]][position[3]] = 2 def inside(x,y):#判断是否跑出棋盘 return 1 <= x and 8 >= x and 1 <= y and 8 >= y Smin = 30#设置一个较大的数来做为最大步数，因为棋盘只有8*8，所以30就足够了 def find(l,X,Y,N=0): global Smin#定义全局变量 if N >= Smin:#超过最大步数就结束本次递归 return if l[X][Y] == 2 and N < Smin:#如果到达了终点且步数小于最大步数，则更新最大步数，减少递归次数 Smin = N return for i in d:#依次获取八个方向 x = X + i[0]#更新棋子下一步位置 y = Y + i[1] if inside(x,y) and l[x][y] != 1:#判断棋子是否走出边界或重复已走过的路 if l[x][y] != 2:#不加这个判断条件会将终点给覆盖掉，从而跑不出结果 l[x][y] = 1 find(l,x,y,N+1) l[x][y] = 0 else: find(l,x,y,N+1) find(l,position[0],position[1],0) if Smin == 30:#等于30则表示没找到路线到达终点 Smin = -1 print(Smin)

kAc给糖果你吃
??这道题没什么可以说的，水题，亏我还看了好久，以为有什么坑QAQ
??直接用python自带的排序函数，然后取最大的m个就行了

n,m = map(int,input().split()) A = list(map(int,input().split())) if n <= m: print(sum(A)) elif m == 0: print(0) else: A.sort() print(sum(A[m:]))

数的潜能
??这道题是看一位大佬解决的，代码也完全一样的，觉得挺完美的了，没啥能修改所以就直接搬过来了，后面给出大佬链接（如果大佬不乐意可联系我立删）

num = int(input()) time, res = divmod(num, 3) def quick_power(basic, time, mod=5218):#快速幂 result = 1 while time: if time & 1:#对应位数是否为1 result = result * basic % mod#取模，防止指数爆炸 basic = basic ** 2 % mod#同上 time >>= 1 return result if num == 1: result = 1 elif res == 2: result = quick_power(3, time) * 2 elif res == 1: result = quick_power(3, time - 1) * 4 else: result = quick_power(3, time) print(result % 5218)

蓝桥杯算法训练数的潜能 Python 100分
幂运算取模