本文主要是介绍python 基础知识点（蓝桥杯python科目个人复习计划65），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今日复习内容：做题
例题1：遥远的雪国列车
问题描述：
小蓝和小红今天在房间里一起看完了“雪国列车”这部电影，看完之后他们感触颇深，同时他们想到了这样一道题目：
现在有一个数轴，长度为N，编号为1到N，数轴上有M辆列车，列车的起点在L，终点在R。给定你Q次询问，每次询问给定一个区间[l,r]，你要回答出有多少辆列车完全在这个区间内。
输入格式：
第一行输入3个整数N，M,Q。
接下来M行，每行输入两个正整数，代表每辆车的起点和终点。
接下来Q行，每行输入两个正整数，代表你需要回答出的区间列车数量。
输出格式：
输出Q行，每行一个整数，代表区间内的列车数量。
参考答案：
n,m,q = map(int,input().split())
a = [[0]*(n + 1) for i in range(n + 1)]
for i in range(m):l,r = map(int,input().split())a[l][r] += 1
f = [[0]*(n + 1) for i in range(n + 1)]
for le in range(1,n + 1):for i in range(1,n + 1):j = i + le - 1if j > n:continueif le == 1:f[i][j] = a[i][j]elif le == 2:f[i][j] = a[i][j] + f[i + 1][j] + f[i][j - 1]else:f[i][j] = a[i][j] + f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1]
for i in range(q):l,r = map(int,input().split())print(f[l][r])运行结果：
以下是我对此题的理解：
这是一道经典的区间统计问题，我做题的思路如下：
首先，从输入中获取数轴的长度N，列车数量M和查询次数Q；
创建一个二维数组a，用于记录每个区间内列车的数。数组a的行表示列车的起点位置，列表示列车的终点位置。a[i][j]表示在起点为i，终点为j的区间内列车的数量。
遍历输入的每辆列车，然后进行以下操作：
外层循环for le in range(1,n + 1)：遍历区间长度，从长度1开始，逐步增加到长度为N的区间。
内层循环for i in range(1,n + 1)：遍历区间的起点位置，从起点1开始，逐步增加到n。
j = le + i - 1：计算当前区间的终点位置
if j > n :continue：确保区间不会超出范围
if le == 1:当区间程度为1时，直接将这个位置的列车数量赋值给a[i][j]，表示此时完全覆盖的列车数量就是此处的列车数量
elif le == 2:f[i][j] = a[i][j] + f[i +1 ][j] + f[i][j - 1]:即当前区间内列车数量加上左边一个区间和下边一个区间的完全覆盖的列车数量。
else:当le大于2时，就还需要减去左下角的那个重复的列车。
最后，根据给定的询问区间，输出区间内完全覆盖的列车数量。
例题2：课上小游戏
问题描述：
小蓝老师在黑板上写了n个数字，并且是环状排列，也就是说，第i个数字和第i+1个数字是相邻的，同时第n和1个数字是相邻的，每个数字是0到9中的一个，小蓝老师要求合并这n个数字，规则如下：
1.每次只能选择相邻的数字进行合并；
2.a，b两个数合并后的结果是(a * b) mod 10，也就是乘积模10的结果，同时获得[a* b / 10]的分数；
3.最后只剩一个数就结束。
输入描述：
第一行输入一个整数N，表示数字个数；
第二行输入N个整数h1,h2,h3,...,hn，代表N个数的值。
输出格式：
输出一个整数，最大得分。
参考答案：
import os
import sys# 请在此输入您的代码
n = int(input())
a = list(map(int, input().split()))# 环形区间dp ——> 普通区间dp
a = [0] + a * 2# dp[i][j]：区间[i, j]合并成一个值的最大分数
dp = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]# res[i][j]：区间[i, j]合并得到的结果
res = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]
for i in range(2 * n + 1):res[i][i] = a[i]for length in range(2, n + 1):for i in range(1, 2 * n - length + 2):j = i + length - 1for k in range(i, j):res[i][j] = (res[i][j - 1] * a[j]) % 10dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + res[i][k] * res[k + 1][j] // 10)ans = 0
for i in range(1, n + 1):ans = max(ans, dp[i][i + n - 1])print(ans)运行结果：
以下是我对此题的理解：
这道题目主要是使用动态规划，通过递归的计算区间内合并得到的最大分数，最终得到最大的得分。
这个答案有点变态，为了方便我记住，我决定分开再写一遍。
n = int(input()):读取输入的数字个数
a = list(int,input().split())：读取n个数字的值
a = [0] + a * 2：将数字序列变成环状排列
dp = [[0]*(2*n + 1) for i in range(2*n + 1)]：初始化一个二维dp数组，用来计算区间合并得到的最大分数
res = [[0]*(2*n + 1) for i in range(2*n + 1)]：初始化一个二维dp数组，用来计算区间合并得到的结果
res[i][i] = a[i]：初始化单个数字的区间合并结果为其本身
然后就是遍历区间长度和起点位置，这里和上一个题一样
for k in range(i,j)：遍历区间内所有可能的分割点，计算每种情况下的最大分数
res[i][j] = (res[i][j - 1] * a[j])%10：根据合并规则，计算区间[i,j]合并得到的结果
之后就是更新区间[i,j]的最大分数，考虑从分割点k处分开合并的情况。具体如下（结合我写的代码）：
dp[i][j]表示区间[i,j]合并得到的最大分数
res[i][k]表示区间[i,k]合并得到的结果
res[k + 1][j]表示区间[k + 1][j]合并得到的结果
考虑从分割点k处分开合并的情况，可以将区间[i,j]分成[i,k],[k + 1，j]两个部分，分别计算它们的最大分数，并将两部分的最大分数相加，再加上这两部分合并的分数，即res[i,k] * res[k + 1][j] // 10，
这里的res[i,k] * res[k + 1][j] // 10表示分割点k处合并得到的分数，根据题目规定，合并的结果是(a * b)mod 10,同时获得[a * b / 10]的分数，即乘积的十位数部分。
综合起来，dp[i][j]的更新公式就是考虑在每个可能的分割点k处合并分开，计算两部分的最大分数，并将其加上两部分合并时的分数，最终取最大值作为区间[i,j]的最大分数。
OK，今天只做了两个题，下一篇继续！
这篇关于python 基础知识点（蓝桥杯python科目个人复习计划65）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
