当前位置：首页 > article >正文

python 基础知识点（蓝桥杯python科目个人复习计划65）

article 2024/11/6 5:12:28

今日复习内容：做题

例题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 - 1
        if j > n:
            continue
        if 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 - 1
    for k in range(i, j):
      res[i][j] = (res[i][j - 1] * a[j]) % 10
      dp[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)

运行结果：