彩票网站建设平台/什么是信息流广告
💖作者简介：大家好，我是车神哥，府学路18号的车神🥇
⚡About—>车神：从寝室到实验室最快3分钟，最慢3分半（那半分钟其实是等红绿灯）
📝个人主页：车手只需要车和手，压力来自论文_府学路18号车神_CSDN博客
🥇 官方认证：人工智能领域优质创作者
🎉点赞➕评论➕收藏 == 养成习惯（一键三连）😋⚡希望大家多多支持🤗~一起加油 😁
专栏
《蓝桥杯-Python》
每天刷一道题，话不多说，先刷近两年的题吧，现在是2021年的真题了，如果有一起的可以加入我们！！！
一起来刷题，冲击国赛！！！
扫码 我的主页 网页左边下方 群二维码。
加入方式：可以在下方的微信名片加我，然后拉你入群。（记得备注暗号：我要拿国奖）
2021年第十二届蓝桥杯赛题总览
2020年的题就是这些，类型分为两种，分别是结果填空和程序设计，我们每天刷一道题，省赛没问题！
路径 （题目）
（本题总分：10分）
官方练习系统：https://www.lanqiao.cn/problems/1460/learning/
—>【问题描述】
—>【结果描述】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
解析
通过阅读题干，本题——难度中等：⭐⭐⭐
考察类型：动态规划、Dijkstra
考察知识点：最小公倍数、gcd()、math
分析：
路径最短，一般有Dijikstra(迪杰斯特拉算法)和动态规划的方法可以解决。但更推荐动态规划的方法，更简单便捷！！！
- Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。由for循环可知，其时间复杂度是O（n^2）。
艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日），生于荷兰Rotterdam，
计算机科学家，毕业就职于荷兰莱顿大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年AFIPS
Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM
PODC最具影响力论文奖。 ——选自《百度百科：艾兹格·迪科斯彻》
具体算法可以看一个B站重庆小姐姐的4分钟视频讲解（贪心思想），还有一个更好一点的B站视频五分钟，感觉更通俗易懂。
下面直接开干！！！
代码
Python代码实现：
法一：（Dijkstra）
#狄克斯特拉算法
#字典 cost,graph,parents
#1:找到最便宜的结点(未访问)，其邻居开销如有更小，更新（cost,parent）
def lcm(a,b):s=a*bwhile b:a,b=b,a%breturn int(s/a)
graph={}#构图
costs={}
parent={}
for i in range(1,2022):graph[i]={}if i<=2020:for j in range(i+1,i+22):graph[i][j]=lcm(i,j)else:for j in range(i+1,2022):graph[i][j]=lcm(i,j)costs[i]=float('inf')found=[]#查找过的结点
costs[1]=0#开始点w为最便宜的点，价格为0def find(dict):#查找最便宜的结点node,cost=None,float('inf')for k,v in dict.items():if k not in found and v<cost:node,cost=k,vreturn nodenode=find(costs)
while node:spend=costs[node]friend=graph[node]try:for i in friend.keys():if costs[i]>friend[i]+costs[node]:costs[i]=friend[i]+costs[node]parent[i]=nodeexcept:#无邻居,costs会报错，说明已经达到终点,打印即可print(costs[2021])breakfound.append(node)node=find(costs)end=parent[2021]#回溯广搜层数
count=1
while end!=1:count+=1end=parent[end]
print(count) #路径长度10266837，回溯了97次,10266837
法二(动态规划)：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2022/3/8 15:34
# @Author : 府学路18号车神
# @Email ：yurz_control@163.com
# @File : DP.py# 当然也可以用自带的库来计算最小公倍数
import math #导入math库
#print(math.gcd(a,b)) #利用函数求解最大公约数
#print(a*b/math.gcd(a,b)) #利用上面的函数求解最小公倍数 INF = 0x3f3f3f3ff3ff # 定义一个较大的值
N = 2025 # 点的个数，总多取一些
d = [INF for i in range(N)] # 下标i表示第i个点到第一个点的最小的情况的值
d[1] = 0def gcd(a, b):if b == 0:return aelse:return gcd(b, a % b)def lcm(a, b):return int(a * b / gcd(a, b)) # 经典最小公倍数for i in range(1, N): # 从第一个点遍历for j in range(i + 1, min(N, i + 22)): # i每跟新一下 后面21个点就开始跟新保留最小的情况d[j] = min(d[j], lcm(i, j) + d[i]) # 1 到第j个点的距离总是取小的print(d[2021]) # 10266837
可以得出最终的结果为：10266837
由此，我们可以快速得出结果，验证完毕！
今天开刷第 十四 天，难度一般，欢迎大家加入，一起变强，一起自律，一起上国赛！！！
今天的题目一般哈，有不同解法的可以在下面留言哦！~
往期刷题路线：
| 刷题路线 | Detail |
|---|---|
| 2020年 | |
| Day-01 | 门牌制作 |
| Day-02 | 寻找2020 |
| Day-03 | 跑步锻炼 |
| Day-04 | 蛇形填数 |
| Day-05 | 排序 |
| Day-06 | 装饰珠 |
| Day-07 | 成绩统计 |
| Day-08 | 单词分析 |
| Day-09 | 数字三角形 |
| Day-10 | 平面切分 |
| – | – |
| 2021年 | |
| Day-11 | 卡片 |
| Day-12 | 直线 |
| Day-13 | 货物摆放 |
官方刷题练习系统：http://lx.lanqiao.cn/
❤坚持读Paper，坚持做笔记，坚持学习，坚持刷力扣LeetCode❤！！！
坚持刷题！！！冲击国赛
⚡To Be No.1⚡⚡哈哈哈哈
⚡创作不易⚡，过路能❤关注、收藏、点个赞❤三连就最好不过了
ღ( ´･ᴗ･` )
❤