蓝桥杯第20天(Python)(疯狂刷题第3天)

这篇具有很好参考价值的文章主要介绍了蓝桥杯第20天(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.阶乘约数 (大数分解,循环)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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]+=1
         i=i//j
   if i>1:   # 剩下的数是一个质数或者本身就是一个质数 例如10=2*5  17=1*17
      save[i]+=1

ans=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.质因子个数 (大数分解,质数,约数)

 蓝桥杯第20天(Python)(疯狂刷题第3天)

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函数用法)

蓝桥杯第20天(Python)(疯狂刷题第3天)

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)


# gcd(0,a)=a

n=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+1
   print(ans)

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

4.快速幂(Fast_pow,位运算,移位操作)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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次方  转为二进制 1000
   if p&1: #当前位有1
      ans=ans%q * b
   b=b*b%q
   p=p>>1  # 右移即/2
print(ans%q)
   

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

5.最大最小公倍数(贪心,枚举讨论)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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.分解质因数(大数分解,字符串处理函数)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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=i
   ans=[]  # 保存分解的数
   for j in range(2,int(math.sqrt(i))+1):
      if i%j==0:
         while i%j==0:
            ans.append(str(j))
            i=i//j
   if i >1:  # 剩下的质数或者本身是质数没有分解,例如15,5,7
      ans.append(str(i))
   print(str(save)+'='+'*'.join(ans))  # " ".join(list)  list里面的元素需要为字符类型

      
            

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

7.裁纸刀(思维题,内置函数的使用)

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

8.蛇形填数(思维,观察规律)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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

9.最大降雨量(思维题)

蓝桥杯第20天(Python)(疯狂刷题第3天)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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

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

10.排序(字典序)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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

11.聪明的猴子(最小生成树,并查集)

蓝桥杯第20天(Python)(疯狂刷题第3天)蓝桥杯第20天(Python)(疯狂刷题第3天)

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):  # 需要合根,默认合向y
      f[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+=1

   if num==(n-1):  # 已经构建好了最小生成树
      break

ans=0  # 记录能跳的猴子数量
for i in leng:
   if i>=Max:
      ans+=1

print(ans)



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

12.路径(floyd或者dijstra实现)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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:
         break
      dp[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  # 自身到自身的距离为0
   heapq.heappush(hp,(0,s))  # 入堆
   while hp:
      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:
         break
      dp[i].append((j,lcm(i,j))) # 邻居和边长

s=1  # 开始起点
dij(s)
print(dis[2021])

      

13.出差(最短路径,矩阵实现Dijstra算法)

蓝桥杯第20天(Python)(疯狂刷题第3天)

蓝桥杯第20天(Python)(疯狂刷题第3天)

 蓝桥杯第20天(Python)(疯狂刷题第3天)

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=-1
      for j in range(1,n+1):
         if st[j]==0 and (t==-1 or dist[t]>dist[j]):  #找到没处理过得最小距离点
            t=j
      for 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]+w
   gra[v][u]=stay[u]+w


print(dij())
   

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

模板:(邻接表)

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

模板:(矩阵)

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

 Bellman-ford算法

蓝桥杯第20天(Python)(疯狂刷题第3天)

蓝桥杯第20天(Python)(疯狂刷题第3天)

蓝桥杯第20天(Python)(疯狂刷题第3天)

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]=0

for k in range(1,n+1): # 遍历每个点,n个点,执行n轮问路
    for a,b,c in e:  # 检查每条边,每一轮问路,检查所有边
        res=t[b]
        if b==n:
            res=0
        dist[b]=min(dist[b],dist[a]+c+res)  # 更新路径长度

print(dist[n])

14.蓝桥王国(Dijstra算法模板题)

蓝桥杯第20天(Python)(疯狂刷题第3天)

 蓝桥杯第20天(Python)(疯狂刷题第3天)

import heapq  # 导入堆
def dij(s):
    done=[0 for i in range(n+1)]  # 记录是否处理过
    hp=[]  #堆
    dis[s]=0
    heapq.heappush(hp,(0,s))   #入堆,小顶堆
    while hp:
        u=heapq.heappop(hp)[1] #出堆元素结点
        if done[u]: #当前结点处理过
            continue
        done[u]=1
        for i in range(len(G[u])): #遍历当前结点的邻居
            v,w =G[u][i]
            if done[v]:continue
            dis[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算法模板题)

蓝桥杯第20天(Python)(疯狂刷题第3天)蓝桥杯第20天(Python)(疯狂刷题第3天)

import os
import sys
 
# 请在此输入您的代码
#floyd算法,多对多
 
 
def floyd():
  global dp
  for 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]=w
  dp[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])
    continue
  print(-1)
   

Floyd算法模板题,熟练掌握就可以了,floyd用于多对多!文章来源地址https://www.toymoban.com/news/detail-421636.html

到了这里,关于蓝桥杯第20天(Python)(疯狂刷题第3天)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯第六讲--简单dp【例题】

    蓝桥杯官网:蓝桥杯大赛——全国大学生TMT行业赛事 ✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识,此博客为第六讲:简单dp【例题】 本篇博客所包含习题有: 👊 01背包问题 👊 摘花生 👊 最长上升子序列 简单dp【习题】见博客:蓝桥杯第六讲–简单dp【习题】 博客内容以

    2023年04月25日
    浏览(43)
  • 蓝桥杯第十三届决赛真题-左移右移

    题目链接 问题描述 小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3, …N 。 之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一: 左移 x, 即把 x 移动到最左边。 右移 x, 即把 x 移动到最右边。 请你回答经过 M 次操作之后, 数组从左到右每个数是多少? 输

    2023年04月09日
    浏览(43)
  • 蓝桥杯第十三届单片机国赛程序

    写在前面: 做完总体来说感觉一年比一年难了(估计是被骂的),虽然十三届用的底层少,但是做起来困难重重。 最难的难点在于定时器安排问题。15F2K60S2系列单片机只有三个定时器,本届题目考到了频率测量、超声波、PWM输出,再加上刷新,每一个都需要一个定时器,比

    2024年02月08日
    浏览(49)
  • 蓝桥杯第十四届蓝桥杯模拟赛第三期考场应对攻略(C/C++)

    这里把我的想法和思路写出来,恳请批评指正! 目录 考前准备 试题1: 试题2: 试题3: 试题4: 试题5: 试题6: 试题7: 试题8: 试题9: 试题10: 总结: 考前五分钟,开十个源文件,并把头文件等必须写的部分写出来,写完的程序一定要有顺序地保留 问题描述 请找到一个

    2024年02月02日
    浏览(137)
  • 【蓝桥杯嵌入式】蓝桥杯第十二届省赛程序真题,真题分析与代码讲解

    🎊【蓝桥杯嵌入式】专题正在持续更新中,原理图解析✨,各模块分析✨以及历年真题讲解✨都在这儿哦,欢迎大家前往订阅本专题,获取更多详细信息哦🎏 🎏【蓝桥杯嵌入式】蓝桥杯第十届省赛真题 🎏【蓝桥杯嵌入式】蓝桥杯第十三届省赛程序真题 🪔本系列专栏 -  

    2023年04月15日
    浏览(71)
  • 蓝桥杯第十四届省赛完整题解 C/C++ B组

    没有测评,不知道对不对,仅仅过样例而已 本题总分:5 分 【问题描述】 小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的 范围之内。数组中的元素从左至右如下所示: 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9

    2023年04月13日
    浏览(47)
  • 【蓝桥杯试题】暴力枚举题型

    💃🏼 本人简介:男 👶🏼 年龄:18 🤞 作者:那就叫我亮亮叭 📕 专栏:蓝桥杯试题 有一个 n×m 方格的棋盘,求其方格包含多少正方形、长方形(不包含正方形)。 输入格式 一行,两个正整数 n,m(n ≤ 5000, m ≤ 5000)。 输出格式 一行,两个正整数,分别表示方格包含多少

    2023年04月08日
    浏览(60)
  • Leetcode刷题第八天-回溯

    22:括号生成 链接:22. 括号生成 - 力扣(LeetCode) 括号是一对,所以每一次递归结束条件是字符串长度=2*n 有效括号判断:\\\'(\\\'个数==\\\')\\\'个数时,当前必须是\\\'(\\\',\\\'(\\\'个数==n时,必须是\\\')\\\',其他情况当前位置遍历两边,既可以是\\\'(\\\'又可以是\\\')\\\' generateParenthesis 89:格雷编码 链接:89.

    2024年02月19日
    浏览(34)
  • 30个题型+代码(冲刺2023蓝桥杯)(下)

    最新消息:未更新的题型不会更新在这篇博客,但是会更新在专栏新的文章里。 👂 咱们结婚吧(心动版) - 1个球 - 单曲 - 网易云音乐  又一个被社会磨平棱角灰头土脸的失败者平庸人罢了 -----------------------------------分界线---------------------------- 👂 霜雪千年 - 排骨教主 -

    2023年04月09日
    浏览(43)
  • 30个题型+代码(冲刺2023蓝桥杯)(上)

    最新消息:未更新的题型不会更新在这篇博客,但是会更新在专栏新的文章里。 愿意的可以跟我一起刷,每个类型做1~5题 ,4月前还可以回来 系统复习   AcW需要付费的题,可以考虑上洛谷,New Oj找替代,或者花点钱 目录 🍎注意 🌼前言 🌼一,前缀和 👊(一)3956. 截断数

    2023年04月15日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包