python 基础知识点（蓝桥杯python科目个人复习计划60）_蓝桥杯安全序列

今日复习计划：做题

例题1：可构造的序列总数

问题描述：

构造王国一年一度的构造大赛又开始了，这次构造王国的国王将只给出两个数k和n，需要大家回答出能够构造多少个符合以下条件的序列：

序列的长度为n；

1 <= a1 <= a2 <= ... <= an <= k;

ai是ai - 1的倍数（i >= 2）；

由于答案可能非常大，你需要将它对10^9 + 7取模。

输入格式：

输入两个用空格隔开的整数n和k；

数据范围保证：1 <= n,k <= 2000

输出格式：

输出一个整数表示答案，需要对10^9 + 7取模。

参考答案：

def work():
    mod = int(1e9) + 7
    k,n = map(int,input().split())
    f = [[0] * (k + 1) for i in range(n + 1)]
    e = [[] for i in range(k + 1)]
    for i in range(1,k + 1):
        for j in range(i,k + 1,i):
            e[j].append(i)
 
    for i in range(1,k + 1):
        f[1][i] = 1
    for i in range(2,n + 1):
        for j in range(1,k + 1):
            for v in e[j]:
                f[i][j] = (f[i][j] + f[i - 1][v]) % mod
    ans = 0
    for i in range(1,k + 1):
        ans = (ans + f[n][i]) % mod
    print(ans)
if __name__ == '__main__':
    work()

运行结果：

以下是我对此题的理解：

这道题的整体思路是使用动态规划来解决，通过递推的方式计算满足条件的序列数量。

首先，我们需要定义一个状态f[i][j]，表示长度为i的序列，且最后一个元素为j时满足条件的序列数量；

我们使用一个额外的二维列表e来存储每个数的因数列表，即e[j]存储了j的所有因数；

初始化长度为1的序列，对于每个数i，仅有一种情况，即每个元素都是i；

对于长度大于1的序列，我们通过动态规划来计算。

遍历长度为i的序列，对于每个数j，再遍历其因数列表e[j]中的每个因数v，更新f[i][j]为前一个i - 1的序列以v结尾的情况的总和，并对结果取模。

最后，遍历所有长度为n的序列，累加其对应的所有情况的数量，并对结果取模，就能得到最终答案了。

---

例题2：最快洗车时间

问题描述：

小蓝开了洗车行，有n辆车需要清洗，第i辆车清洗需要ti分钟。小蓝购买了2台自动洗车机，可以同时清洗车辆。但由于两台洗车机共用一个电源，所有必须所有车辆都清洗完毕后从才能关掉电源。

请问从第一辆车开始清洗后，忽略洗车之外的时间，至少需要多长时间才能关闭电源？

输入格式：

第一行输入一个整数n，表示需要清洗的车辆数；

第二行输入n个整数，表示每辆车的清洗时间；

数据范围保证：1 <= n <= 100,1 <= ti <= 1000

输出描述：

输出一个答案，表示最少需要的时间。

参考答案：

import math
ans = math.inf
n = int(input())
t = [0] + list(map(int,input().split()))
tot = sum(t)
f = [[False] * (tot + 1) for i in range(n + 1)]
f[0][0] = True
for i in range(1,n + 1):
    for j in range(tot + 1):
        f[i][j] = f[i - 1][j]
        if j >= t[i]:
            f[i][j] |= f[i - 1][j - t[i]]
for i in range(tot + 1):
    if f[n][i]:
        ans = min(ans,max(i,tot - i))
print(ans)

运行结果：

 

以下是我对此题的理解：

这道题也是用动态规划来做，以下是我写代码时的笔记。

1.初始化变量和数组

ans = math.inf：初始化一个变量ans，用于存储最终的最小时间，初始值为正无穷

n = int(input())：从标准输入中读取正整数n，表示需要清洗的车辆数

t = [0] + list(map(int,input().split()))：从标准输入中读取n个整数，表示每辆车的清洗时间，在前面加一个0，是为了让索引从1开始。

tot = sum(t)：计算所有车辆清洗时间的总和

2.动态规划状态数组

f是一个二维数组，其中f[i][j]表示前i辆车是否可以在总清洗时间为j的情况下完成清洗，初始化时，所有状态都设为False。

3.状态转移

使用两个嵌套循环，分别遍历车辆数和清洗时间

f[i][j] = f[i - 1][j]：该状态可以继承上一个状态，即不清洗该车辆。

if j >= t[i]：检查是否可以清洗当前车辆，如果总时间大于等于当前车辆所需的清洗时间，则可以清洗

f[i][j] = f[i - 1][j - t[i]]：当前状态取决于前一个状态减去当前 车辆清洗时间的状态

4.计算当前最少关闭电源时间

遍历所有可能的总清洗时间i，如果最后一辆车的清洗状态为真，f[n][i]，则更新ans为当前时间i与剩余时间tot - i的最大值

5.输出最小关闭电源时间

---

例题3：安全序列

问题描述：

小蓝是工厂里的安全工程师，他负责安放工厂里的危险品。

工厂是一条直线，直线上有n个空位，小蓝需要将若干个油桶放置在n个空位上，每两个油桶之间至少需要k个空位隔开，现在小蓝想知道有多少种放置方案，你可以编写一个程序帮助他吗？

由于这个结果很大，你需要对10^9 + 7取模。

输入格式：

第一行包括两个正整数n和k，分别表示n个空位和k个隔开的空位。

输出格式：

输出共一行，包含一个整数，表示放置的方案数对10^9 + 7取模。

参考答案：

mod = int(1e9) + 7
n,k = map(int,input().split())
f = [0] * (n + 1)
f[0] = 1
for i in range(1,n + 1):
    f[i] = f[i - 1]
    if i >= (k + 1):
        f[i] = (f[i] + f[i - (k + 1)]) % mod
    else:
        f[i] = (f[i] + 1) % mod
print(f[n])

运行结果：

---

OK，今天就先写这些，我还要学别的东西，下一篇继续！