> 文档中心 > 【蓝桥杯考前一天总结PYthon终结篇】

【蓝桥杯考前一天总结PYthon终结篇】


最短路之Floyd:

适用领域:既可以是有向图也可以是无向图,权重可以为负,通常用来求各顶点之间的距离(多源)

缺点就是时间复杂度高,加上Python本身跑得慢....就祈祷这次题数据量不要太大

优点就是比起狄克斯特拉算法,简单地多,代码量少,容易上手

板子

n=int(input())#这个根据题意设置,表示结点个数edge=[[float('inf')]*n for i in range(n)]#初始化所有边权为无穷大#根据题意更新edge[i][j]#更新的时候,如果有无向图需要edge[i][j]=edge[j][i]这样设置,否则不用#三重循环 结束for k in range(n):    for i in range(n): for j in range(n):     edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])

最短路之狄克斯特拉:

适用领域:既可以是无向图也可以有向图,权值必须非负,求某个顶点到其他顶点的最短距离(单源)

缺点:写起来会稍微麻烦一点比起Floyd 东西比较多

优点:跑的挺快的,数据量比较大的时候也能用Python解决

板子:

n=int(input())#根据题意 n代表结点个数edge={}#edge[i]={x:费用1,y:费用1....} 存结点之间的费用cost=[]#cost[i]代表结点i到出发点的最短开销s=set()#集合s用于存储处理过的结点def find_node():#find_node函数用于寻找未被处理过的最便宜的结点    node,spend=None,float('inf')    for i in range(n): if cost[i]<=spend and i not in s:#     node,spend=i,cost[i]    return nodewhile node:#只要还有结点未被处理    for i in edge[node]:#遍历node的邻居 cost[i]=min(cost[i],cost[node]+edge[node][i])    s.add(node)    node=find_nodeprint(#根据你的需要输出出发点到某个结点i的费用cost[i])    #此外补充一个,如果题还要我们求最短路径上边的个数#只需外加一个字典pre 每当更新cost[i]时,创建一个键值对#最后通过终点逆向遍历统计次数即边数 输出即可

取模运算法则:

知识点:若x>y>0,若p=x%y,那么p一定小于y,即p∈[0,y-1] 

两届连续考察了这个知识点!!重视

二分答案、Bisect模块:

题目中出现最大的某某的最小值,最小的某某的最大值,没有思路时,往往可以直接去二分答案

板子:check函数是核心

#l,r根据题意设置 红蓝区域自己定义划分def check(x):    #假设x为答案    #题目一般有有个约束条件    #如果通过某种手段使得在x的条件下存在符合约束条件的解    #那么就是可行解while l+1!=r:    mid=(l+r)//2    if check(mid): r=mid    else: l=mid#取l还是r依据需要

Bisect模块:(只能用在升序数组,它源码写的时候就默认这个了QWQ)

import bisecta=[0,1,2,3,3,3,5]#一段升序数组bisect.bisect(a,b)#返回数组a中最后一个<=b的数字的下标+1#bisect.bisect(a,3)返回6bisect.bisect_left(a,3)#返回数组中第一个等于3的下标#bisect.bisect_left(a,3)返回3#如果不存在等于3的,和bisect.bisect等效bisect.bisect_right(a,3)#返回数组中最后一个等于3的下标+1#bisect.bisect_right(a,3)返回6#如果不存在等于3的,和bisect.bisect等效

这个模块通常用于查询某个序列内 属于某个区间的数的个数,>=p还是<=p?效率很高

当然也可以直接用列表解析式+len函数,但效率不高

len([i for i in a if i<=p])#p自己设定

[贡献值法]:研究单个元素被引入后对结果的增量,实际上是把复杂的大问题转化为一个个小问题,当问题难以入手时,可以考虑这个做法

并查集:

板子

n=int(input())#根据题意输入节点个数#初始化parent=[i for i in range(n)]#查找def find_root(x):    if parent[x]!=x: parent[x]=find_root(parent[x])    return parent[x]#合并def uion(x,y):    x_root,y_root=find_root(x),find_root(y)    parent[x_root]=y_root

用途很广,考的频率也高哦,考试的时候多往这里想一想

最小生成树:

适用场景:对于有n个顶点的连通图,其中只有n-1条边的连通子图即最小生成树

常常这n-1条边被赋予了权值 我们需要求出最小权值和

板子:里面有并查集的内容!

n=int(input())edge=[]#edge[i]=[a,b,c]代表i这条边连接了a,b,权值为cans=0#权值和edge.sort(key=lambda x:x[2])#按边权升序排序for x in edge:#遍历所有边    a,b,c=x[0],x[1],x[2]    if find_root(a)!=find_root(b) and j<=n-1:#两顶点不连通且当前边数小于n-1 ans+=x[2]#权值累加 union(a,b) j+=1print(ans)

拓扑排序: 

适用场景:有向图,检测环,有向无环图一定有拓扑序列。

板子:

graph={'a':'bc','b':'ef'    }#graph的key表示入边,value表示被指向的点indegrees=dict((i,0) for i in graph)#初始化入度为0for i in graph:    for j in graph[i]:#遍历i的邻居 邻居入度+1 indegrees[j]+=1stack=[]#存入度为0的点seq=[]#存拓扑序列for i in indegrees:    if indegrees[i]==0:#入度为0 stack.append(i)#入栈while stack:#栈不为空    t=stack.pop(0)    seq.append(t)    for i in graph[t]: #邻居入度-1 indegrees[i]-=1 if indegrees[i]==0:     stack.append(i)     if len(seq)==len(graph):    #无环else:    #有环

有关DP的,这里直接引用小蓝的笔记啦,也就是这次的榜一~写的很棒!

【动态规划】内容很详实,左侧传送门@小蓝刷题

 感谢蓝桥杯一路陪伴 感谢对小郑的支持

希望明天和我一起冲击Python组的伙伴一举拿下省一 一起见证国赛!

愿所有的努力都有回报!