2022年 11月 9日

蓝桥杯 真题演练(二) python 动态DP 最小公倍数

在这里插入图片描述
距离蓝桥杯竞赛还剩36天,每天进步一点点,积少成多,加油!☀️☀️

大家好,我是 @愿此后再无WA,可以叫我小A😊😊,时刻这么多天我又回来啦,接下来我会好好刷题出好题解的!!一起加油努力呀!!🌟🌟

时间显示

在这里插入图片描述

⭐️⭐️这是竞赛的第一道大题,相对来说会比较简单,所以我们不要害怕题目,不要被1970,毫秒这些字眼给迷惑住了,一口气把题目看完之后你就会发现其实题目就是看起来难而已。

⭐️⭐️题目大意就是给一个毫秒数(但是毫秒数不用显示,相当于就是给一个秒数),让你将其转换成24小时制的时间显示。

⭐️⭐️ 解题思路:给出时间,我们求的顺序应该是 时,分,秒。先求出有多少个小时,除完后剩下的余数就用来求分钟数,最后来求秒数。期间要注意,题目给的时间可能会超过24小时的情况,因此得到小时数后还有对小时数取余,得到小于24小时的部分。

time = int(input())

time = time // 1000  # 题目说毫秒可以直接舍去

h = time // 3600 % 24   # 总时间除以3600可以得出一共有几个小时,避免超过24小时,所以还要对24除余求余数部分

m = time % 3600 // 60  # 总时间对3600除余的余数部分即为剩下的秒数,再整除60即可得到分钟数

s = time % 60  # 总时间除余60得到的就是秒数

print("%02d:%02d:%02d" % (h,m,s))  # 题目要求不足两位数要补0,那么就能使用这种格式表示

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

路径

在这里插入图片描述

💦💦这是一道填空题,但可以把它当做一道大题来做。题目的意思简单理解为 每个节点的距离是他们的最小公倍数,而节点与节点之间的编号之差不能大于21,最后求的是节点1到节点2021的最短距离。

💦💦 这里就涉及到了一个知识点——最小公倍数,为求最小公倍数,有个公式是 最小公倍数 = 两数乘积 / 最大公约数。而最大公约数可以使用辗转相除法求解。

💦💦 接着我们应该怎么做呢?这题可以用动态DP打表的方式得出答案。如果不清楚DP数组的朋友可以点击这里。提到DP我也说一下,最近几年蓝桥杯试题的难度增长趋势是非常明显的,因此动态DP应该是要成为我们的必备技能。(❗️❗️所以我强烈建议不了解DP数组的朋友把DP学会❗️❗️)

💦💦 如果你已经知道了如何使用动态规划的DP数组,那么这道题就变得容易起来,每个中间节点(假设是i)无非就两个动作:找到通往 i 节点的最近节点确定 i 节点与下一节点的距离。
在这里插入图片描述
说完了中间部分的节点,现在就来说一下两边的节点,因为节点1是所有数的约数,那么它可以直接得出 2~22 的距离了,就是节点值本身。而最后一个数2021,它的动作就是判断在它的连接范围内哪个距离最短,哪个短就选哪个。

💦💦 我们先看一下二维DP的思路

# 试题D:路径 答案:10266837

# 最小公倍数LCM(least common multiple)的辗转相除法。

def lcm(a,b):
    if a > b:
        
        a,b = b,a
        
    mul = a * b
    
    # 不断用大的数除以小的数取余数部分直到最后能够整除为止。
    while a > 0: 
        
        a,b = b % a, a
        
    return mul// b 
 
target = 2021

dp= [[float("inf")] * (target+1) for i in range(target+1)] # 创建列表的两种写法

# 初始化状态
for i in range(1,23):  # 1能到的最远距离是22,因为22-1不大于21,所以这里右区间是23
    
    dp[1][i] = i   # 1 与 n 的最小公倍数必定是 n

for i in range(2,target+1):   # 填表

    # 从第i个数开始只填绝对值小于21的部分
    for j in range(i,i+22):  
    
        # 当超出目标值2021时终止循环
        if j > target:
            break
        # 当j等于i时,寻找上一个距离i最近的节点,第一个动作
        if j == i:
            # 寻找前面21范围以内的数,找出上一节点到i节点的最短路径
            for k in range(1,22):
                if i - k > 0:
                    # 取二者最小值
                    dp[i][j] = min(dp[i][j],dp[i-k][j])
                else:
                    break
        # 第二个动作就是确定i的上一节点到i的下一节点的距离
        else:
            # dp[i][i]表示上一个节点到节点i的最短距离,然后上一节点又表示上上节点到该节点的距离,然后上上...
            # 其实就是节点1到节点i的距离
            # lcm(i,j)表示i到下一节点的距离
            # dp[i][j]表示节点1到节点j的路径
            dp[i][j] = lcm(i,j) + dp[i][i] 
# 最后打印结果          
print(dp[target][target])
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

💦💦对于二维DP而言,有些地方是可以优化的,可以一气呵成,将两个动作合并成一个动作,转换成一维DP。下面我们看一下代码实现。

# 试题D:路径 答案:10266837

# 最小公倍数LCM(least common multiple)的辗转相除法。

def lcm(a,b):
    if a > b:
        
        a,b = b,a
        
    mul = a * b

    # 不断用大的数除以小的数取余数部分直到最后能够整除为止。
    
    while a > 0: 
        
        a,b = b % a, a
        
    return mul// b 
 
target = 2021

dp=[float('inf') for i in range(target+1)]

# 初始化状态
for i in range(1,23):  # 1能到的最远距离是22,因为22-1不大于21,所以这里右区间是23
  
    dp[1][i] = i   # 1 与 n 的最小公倍数必定是 n

# 接着就是按着前面的数据进行填表了
for i in range(23,target+1):
    for j in range(1,22):
        if i - j > 0:
            # dp[i-j] 表示上一节点的信息 其实就是节点1到上一节点的距离
            # lcm(i-j, i) 表示上一节点到节点i的距离
            dp[i] = min(dp[i], dp[i-j]+lcm(i-j, i))
print(dp[target])
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36