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

最短路之Floyd: 适用领域:既可以是有向图也可以是无向图,权重可以为负,通常用…

最短路之Floyd:

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

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

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

板子:

最短路之狄克斯特拉:

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

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

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

板子:

取模运算法则:

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

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

二分答案、Bisect模块:

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

板子:check函数是核心

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

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

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

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

并查集:

板子

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

最小生成树:

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

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

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

拓扑排序:

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

板子:

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

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

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

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

愿所有的努力都有回报!

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/1890.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部