蓝桥杯第19天（Python）（疯狂刷题第3天）

题型：

1.思维题/杂题：数学公式，分析题意，找规律

2.BFS/DFS：广搜（递归实现），深搜（deque实现）

3.简单数论：模，素数（只需要判断到 int（sqrt（n））+1），gcd，lcm，快速幂（位运算移位操作），大数分解（分解为质数的乘积）

4.简单图论：最短路（一对多（Dijstra，临接表，矩阵实现），多对多（Floyd，矩阵实现）），最小生成树（并查集实现）

5.简单字符串处理：最好转为列表操作

6.DP：线性DP，最长公共子序列，0/1背包问题，最长连续字符串，最大递增子串

7.基本算法：二分，贪心，组合，排列，前缀和，差分

8.基本数据结构：队列，集合，字典，字符串，列表，栈，树

9.常用模块：math，datetime，sys中的设置最大递归深度（sys.setrecursionlimit(3000000)），collections.deque（队列），itertools.combinations（list,n）（组合），itertools.permutations（list,n）（排列）  heapq（小顶堆）

目录

题型：

刷题

1.阶乘约数 （大数分解，循环）

2.质因子个数 （大数分解，质数，约数）

3.等差数列（gcd函数用法）

4.快速幂（Fast_pow,位运算，移位操作）

5.最大最小公倍数（贪心，枚举讨论）

6.分解质因数（大数分解，字符串处理函数）

7.裁纸刀（思维题，内置函数的使用）

8.蛇形填数（思维，观察规律）

9.最大降雨量（思维题）

10.排序（字典序）

11.聪明的猴子（最小生成树，并查集）

12.路径（floyd或者dijstra实现）

13.出差（最短路径，矩阵实现Dijstra算法）

14.蓝桥王国（Dijstra算法模板题）

15.蓝桥公园 （Floyd算法模板题）

刷题

1.阶乘约数 （大数分解，循环）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)#写法一
save=[0]*101  # 大数分解
for i in range(1,101):for j in range(2,int(math.sqrt(i))+1):  # 质数从2开始while i%j==0:  # 质数分解save[j]+=1i=i//jif i>1:   # 剩下的数是一个质数或者本身就是一个质数 例如10=2*5  17=1*17save[i]+=1ans=1
for i in save:ans*=(i+1)
print(ans)# 写法二
##MAXN = 110  
##cnt = [0] * MAXN   #记录对应质数幂次
## 
##for i in range(1, 101):
##    x = i
##    # 质因子分解
##    j = 2
##    while j * j <= x:
##        if x % j == 0:  # 是一个质数约数
##            while x % j == 0:  #类似埃式筛
##                x //= j
##                cnt[j] += 1
##        j += 1
##    if x > 1:
##        cnt[x] += 1
## 
##ans = 1
##for i in range(1, 101):
##    if cnt[i] != 0:
##        ans *= (cnt[i] + 1)  # 0 也是一种选择
## 
##print(ans)

 两种实现方法，因为是100！，所以需要遍历1-100进行大数分解，注意质数是从2开始的，1不是质数，只需要遍历2 - int( sqrt(n) ）区间是否有n的因子，python取不到后面一位所以要加1，没得说明他是质数，同时如果分解后大于1说明没有被分解完，剩下的为质数，例如10，不是质数会变为1，例如4,9

2.质因子个数 （大数分解，质数，约数）

 

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)#对一个数进行大数分解
ans=0
n=int(input())
for i in range(2,int(math.sqrt(n))+1):if n%i==0:  #发现质数ans+=1#print(i)  # 打印质数约数while n%i==0:  # 消除这个质数n=n//i
if n>1:#print(n)  # 打印质数约数ans+=1
print(ans)

送分题，会了第一题这道题就是秒出答案，只需要分解这一个数就行了，只需要求有多少个质数，注意判断分解后如果剩下的数大于1，说明还剩下了一个质数，答案需要加1.

3.等差数列（gcd函数用法）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)# gcd(0,a)=an=int(input())
A=list(map(int,input().split()))
d=0
for i in range(len(A)-1):d=math.gcd(d,A[i+1]-A[i])#print(d) #打印d# 需要处理d==0的情况
if d==0:print(n)
else:ans=(max(A)-min(A))//d+1print(ans)

送分题，但是需要仔细判断情况，之前一直漏掉了d==0时的情况，没有考虑周全，出现÷0错误，需要注意gcd（0，a）= a，当不确定长度，边界范围的时候自己举例来确定。

4.快速幂（Fast_pow,位运算，移位操作）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)b,p,q = map(int,input().split())
ans=1
while p:  # 8次方  转为二进制 1000if p&1: #当前位有1ans=ans%q * bb=b*b%qp=p>>1  # 右移即/2
print(ans%q)

算是送分题，需要掌握位运算，左移乘2右移除2，使用while语句循环的时候注意在最后要改值，例如左加右减，右移左移，防止死循环。

5.最大最小公倍数（贪心，枚举讨论）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)n=int(input())
# 第一时间想到 n*(n-1)*(n-2)
# 当n为奇数  最大值 n*(n-1)*(n-2)
# 当n为偶数  n和n-2可以约分
# n*(n-1)*(n-3)   (不能被3整除)
# (n-1)*(n-2)*(n-3） （能被3整除）if n%2==1:print(n*(n-1)*(n-2))
else:if n%3==0:  #能被3整除print((n-1)*(n-2)*(n-3))else:print(n*(n-1)*(n-3))

 枚举所有情况，首先按照贪心想法取3个最大值，然后在讨论特殊情况，例如有约数这些，要找互质的。因为求最小公倍数最大值。

6.分解质因数（大数分解，字符串处理函数）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)a,b=map(int,input().split())
for i in range(a,b+1):save=ians=[]  # 保存分解的数for j in range(2,int(math.sqrt(i))+1):if i%j==0:while i%j==0:ans.append(str(j))i=i//jif i >1:  # 剩下的质数或者本身是质数没有分解，例如15，5，7ans.append(str(i))print(str(save)+'='+'*'.join(ans))  # " ".join(list)  list里面的元素需要为字符类型

 遍历这些数，对每一个数进行大数分解，难点在于知道分解后如果n值＞1，说明分解后剩下了一个质数或者本身是质数不能分解为其他质数，然后就是字符串拼接操作，join（）函数需要连接元素为字符串的才可以。

7.裁纸刀（思维题，内置函数的使用）

 没什么难点，属于送分，需要读懂题意，就只有两种分法，使用内置函数min（）取最小值就可以了，送分！！

8.蛇形填数（思维，观察规律）

 求的是对角线上元素，观察对角线上元素的规律，即 +4  +8   +12  ，发现规律了直接套一个循环就可以了。

9.最大降雨量（思维题）

 34   --------->  49-15=34，上面手误了

 思维题，注意重点，即两个中位数，不确定的时候举例，举特例来证明结论。

10.排序（字典序）

 理解字典序的含义，即 'a'>'b'，' a' > 'ab'，'ab'>'b'。这道题要求最短同时按照字典序，所以固定了答案，同时需要了解全排列，即 N*（N-1）/2   ，即 bca 排列成abc全排列 3*2/2=3

11.聪明的猴子（最小生成树，并查集）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)def find(x):if x==f[x]:return f[x]else:f[x]=find(f[x])return f[x]def merge(x,y):if find(x)!=find(y):  # 需要合根,默认合向yf[find(x)]=find(y)  # x的根指向y的根m=int(input()) # 猴子树
leng=list(map(int,input().split()))  # 存储跳跃距离n=int(input()) # 边数
dis = [0] # 存储坐标
for i in range(n):  dis.append(list(map(int,input().split())))edge=[] #存储边
for i in range(1,n+1):for j in range(i+1,n+1):w=math.sqrt((dis[i][0]-dis[j][0])**2+(dis[i][1]-dis[j][1])**2) #计算距离edge.append((i,j,w))   # 添加边，总共添加n*（n-1）/2条边
edge.sort(key=lambda x:x[2])  # 边从小到大排序Max=0
num=0  # 当前处理了多少条边
f=[ i for i in range(n+1)]
for i in edge:if find(i[0]) !=find(i[1]):   # 最小生成树算法处理merge(i[0],i[1])Max=max(Max,i[2])   #在遍历过程中记录下最长边num+=1if num==(n-1):  # 已经构建好了最小生成树breakans=0  # 记录能跳的猴子数量
for i in leng:if i>=Max:ans+=1print(ans)

 熟悉并查集的使用，最小生成树的构建方法，学会通过并查集，使用Kruskal Algorithm算法，即边从大到小排序，依次遍历最短边来构建最小生成树的方法来构建最小生成树。

12.路径（floyd或者dijstra实现）

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)# 初始化边         
dp=[[2**100]*2030 for i in range(2030)]def lcm(a,b):return a//math.gcd(a,b)*b
# 赋初值
for i in range(1,2022):for j in range(i+1,i+22):  # 取不到最后一位if j>2021:breakdp[i][j]=lcm(i,j)# floyd 算距离
for k in range(1,2022):for i in range(1,2):for j in range(1,2022):dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])print(dp[1][2021])

floyd算法求得是多对多，但是时间复杂度为3阶多项式复杂度，Dijstra复杂度低一些，求的是1到多，floyd算法可以转换为求1到多，多到多，多到1。本题难点在于floyd算法的掌握，同时需要注意，floyd是通过矩阵实现的。 

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)# Dijstr实现
def lcm(a,b):return a//math.gcd(a,b)*b
def dij(s):done=[0]*2022  # 标记是否处理过hp=[]dis[s]=0  # 自身到自身的距离为0heapq.heappush(hp,(0,s))  # 入堆while heapq:u=heapq.heappop(hp)[1]  # 出堆元素结点，边最小if done[u]==0: # 没有被处理过done[u]=1#for i in dp[u]:  # 遍历u的邻居  i:(v,w)for i in range(len(dp[u])):  # 遍历u的邻居  i:(v,w)v,w=dp[u][i]if done[v]==0: # 没有被处理过dis[v]=min(dis[v],dis[u]+w)heapq.heappush(hp,(dis[v],v))dp=[[] for i in range(2022)]  # 邻接表
dis=[2**100] * 2022  # 初始
# 邻接表更新
for i in range(1,2022):for j in range(i+1,i+22):if j>2021:breakdp[i].append((j,lcm(i,j))) # 邻居和边长s=1  # 开始起点
dij(s)
print(dis[2021])

13.出差（最短路径，矩阵实现Dijstra算法）

 

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)def dij():dist[1]=0  #很重要for _ in range(n-1): # 还有n-1个点没有遍历t=-1for j in range(1,n+1):if st[j]==0 and (t==-1 or dist[t]>dist[j]):  #找到没处理过得最小距离点t=jfor j in range(1,n+1):dist[j]=min(dist[j],dist[t]+gra[t][j])  # t-j的距离，找最小值st[t]=1  # 标记处理过return dist[n]n,m=map(int,input().split())#下标全部转为从1开始
stay=[0]+list(map(int,input().split()))
stay[n]=0   
gra = [[float('inf')] * (n+1) for _ in range(n+1)]
dist = [float('inf')] * (n+1)
st=[0]*(n+1)  # 标志是否处理for i in range(m):u,v,w=map(int,input().split()) #这里重构图gra[u][v]=stay[v]+wgra[v][u]=stay[u]+wprint(dij())

本题难点在于重新搭建图，即将在每个城市滞留的时间更新到图里面。同时，DIjstra算法也很重要。

模板：（邻接表）

通过heapq实现，临接表存储（v，w），使用小顶堆存储，每次出堆得到初始距离最小距离的顶点，然后判断他的临接点是否被处理过，没有就更新这些临接点的距离，然后将计算后的距离入堆，要有标记矩阵，距离矩阵，邻接表

模板：（矩阵）

通过矩阵实现存储边信息，进行n-1次循环处理剩下的点，寻找没处理过得距离初始点最短的点，然后通过他更新其他点离初始点距离值，找到最小值。需要标记矩阵，距离矩阵，，矩阵存储边。

 Bellman-ford算法

 

n,m=map(int,input().split())
t=[0]+list(map(int,input().split()))
e=[]  #简单的数组存边for i in range(1,m+1):a,b,c = map(int,input().split())e.append([a,b,c])  # 双向边e.append([b,a,c])dist=[2**50]*(n+1)
dist[1]=0for k in range(1,n+1): # 遍历每个点，n个点，执行n轮问路for a,b,c in e:  # 检查每条边，每一轮问路，检查所有边res=t[b]if b==n:res=0dist[b]=min(dist[b],dist[a]+c+res)  # 更新路径长度print(dist[n])

14.蓝桥王国（Dijstra算法模板题）

 

import heapq  # 导入堆
def dij(s):done=[0 for i in range(n+1)]  # 记录是否处理过hp=[]  #堆dis[s]=0heapq.heappush(hp,(0,s))   #入堆，小顶堆while hp:u=heapq.heappop(hp)[1] #出堆元素结点if done[u]: #当前结点处理过continuedone[u]=1for i in range(len(G[u])): #遍历当前结点的邻居v,w =G[u][i]if done[v]:continuedis[v]=min(dis[v],dis[u]+w)  # 更新当前结点邻居的最短路径heapq.heappush(hp,(dis[v],v))n,m = map(int,input().split())#
s=1  # 从1开始访问
G=[[]for i in range(n+1)]   #邻接表存储
inf = 2**50
dis = [inf]*(n+1) #存储距离
for i in range(m):# 存边，这里是单向边u,v,w = map(int,input().split())G[u].append((v,w))  #记录结点u的邻居和边长dij(s)
for i in range(1,n+1):if dis[i]==inf:print("-1",end=' ')else:print(dis[i],end=' ')

模板题，需要熟练掌握和牢记，这是通过heapq小顶堆实现的，掌握模板就可以了

15.蓝桥公园 （Floyd算法模板题）

import os
import sys# 请在此输入您的代码
#floyd算法，多对多def floyd():global dpfor i in range(1,n+1):for j in range(1,n+1):for k in range(1,n+1):dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])n,m,q = map(int,input().split())
inf=2**120
dp=[[inf]*(n+1) for i in range(n+1)]
choice=[]
for i in range(m):u,v,w=map(int,input().split())dp[u][v]=wdp[v][u]=w
for i in range(q):s,d = map(int,input().split())choice.append((s,d))
floyd()
for s,d in choice:if dp[s][d]!=inf:print(dp[s][d])continueprint(-1)

Floyd算法模板题，熟练掌握就可以了，floyd用于多对多！