2023年NOC决赛-加码未来编程赛项决赛模拟题-Python模拟题--卷6

**2023年NOC决赛-加码未来编程赛项决赛模拟题-Python模拟题--卷6**

**一、基础题目**

###1.1 判断是否为闰年#### 题目描述判断一个年份是否为闰年。

#### 输入输出格式输入: 年份（整数）
输出: 是否为闰年（布尔值）

#### 示例代码

def is_leap_year(year):
 """
 判断一个年份是否为闰年。
 :param year: 年份（整数）
 :return: 是否为闰年（布尔值）
 """
 if year %4 ==0 and (year %100 !=0 or year %400 ==0):
 return True else:
 return False# 测试用例print(is_leap_year(2020)) # Trueprint(is_leap_year(2019)) # False

###1.2 数组中最长的连续子数组#### 题目描述给定一个整数数组，找出其中最长的连续子数组。

#### 输入输出格式输入: 整数数组输出: 最长的连续子数组（列表）

#### 示例代码

def longest_consecutive_subarray(nums):
 """
 找出整数数组中最长的连续子数组。
 :param nums: 整数数组 :return: 最长的连续子数组（列表）
 """
 if not nums:
 return []
 nums.sort()
 max_length =1 max_subarray = [nums[0]]
 for i in range(1, len(nums)):
 if nums[i] == nums[i -1] +1:
 max_length +=1 max_subarray.append(nums[i])
 else:
 max_length =1 max_subarray = [nums[i]]
 return max_subarray# 测试用例print(longest_consecutive_subarray([1,9,3,10,4,20,2])) # [1,9,3,10,4,20]

###1.3 最大子序列和#### 题目描述给定一个整数数组，找出其中最大子序列的和。

#### 输入输出格式输入: 整数数组输出: 最大子序列和（整数）

#### 示例代码

def max_subarray_sum(nums):
 """
 找出整数数组中最大子序列的和。
 :param nums: 整数数组 :return: 最大子序列和（整数）
 """
 if not nums:
 return0 max_sum = float('-inf')
 current_sum =0 for num in nums:
 current_sum = max(num, current_sum + num)
 max_sum = max(max_sum, current_sum)
 return max_sum# 测试用例print(max_subarray_sum([-2, -3,4, -1, -2,1,5, -3])) #7

**二、进阶题目**

###2.1 最小生成树#### 题目描述给定一个带权图，找出其中最小的生成树。

#### 输入输出格式输入: 带权图（邻接矩阵）
输出: 最小生成树（列表）

#### 示例代码

import networkx as nxdef min_spanning_tree(graph):
 """
 找出带权图中最小的生成树。
 :param graph: 带权图（邻接矩阵）
 :return: 最小生成树（列表）
 """
 G = nx.Graph()
 for i in range(len(graph)):
 for j in range(i +1, len(graph)):
 if graph[i][j] != float('inf'):
 G.add_edge(i, j, weight=graph[i][j])
 return list(nx.minimum_spanning_tree(G).edges)

# 测试用例graph = [[0,2, float('inf'),6],
 [2,0,3, float('inf')],
 [float('inf'),3,0,1],
 [6, float('inf'),1,0]]
print(min_spanning_tree(graph)) # [(0,1), (1,2), (2,3)]

###2.2 最长上升子序列#### 题目描述给定一个整数数组，找出其中最长的上升子序列。

#### 输入输出格式输入: 整数数组输出: 最长上升子序列（列表）

#### 示例代码

def longest_ascending_subsequence(nums):
 """
 找出整数数组中最长的上升子序列。
 :param nums: 整数数组 :return: 最长上升子序列（列表）
 """
 if not nums:
 return []
 dp = [1] * len(nums)
 for i in range(1, len(nums)):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i] = max(dp[i], dp[j] +1)
 max_length = max(dp)
 max_subsequence = []
 for i in range(len(nums) -1, -1, -1):
 if dp[i] == max_length:
 max_subsequence.append(nums[i])
 max_length -=1 return max_subsequence[::-1]

# 测试用例print(longest_ascending_subsequence([10,9,4,5,7,6,3,8])) # [3,4,5,7,8]

###2.3 最大子矩阵#### 题目描述给定一个整数矩阵，找出其中最大子矩阵。

#### 输入输出格式输入: 整数矩阵输出: 最大子矩阵（列表）

#### 示例代码

def max_submatrix(matrix):
 """
 找出整数矩阵中最大子矩阵。
 :param matrix: 整数矩阵 :return: 最大子矩阵（列表）
 """
 if not matrix:
 return []
 rows = len(matrix)
 cols = len(matrix[0])
 max_sum = float('-inf')
 max_submatrix = []
 for i in range(rows):
 for j in range(cols):
 current_sum =0 for k in range(i, rows):
 for col in range(j, cols):
 current_sum += matrix[k][col]
 if current_sum > max_sum:
 max_sum = current_sum max_submatrix = [[matrix[x][y] for y in range(j, col +1)] for x in range(i, k +1)]
 return max_submatrix# 测试用例matrix = [[1,2,3],
 [4,5,6],
 [7,8,9]]
print(max_submatrix(matrix)) # [[1,2,3], [4,5,6], [7,8,9]]

**三、综合题目**

###3.1 最大子序列和#### 题目描述给定一个整数数组，找出其中最大子序列的和。

#### 输入输出格式输入: 整数数组输出: 最大子序列和（整数）

#### 示例代码

def max_subarray_sum(nums):
 """
 找出整数数组中最大子序列的和。
 :param nums: 整数数组 :return: 最大子序列和（整数）
 """
 if not nums:
 return0 max_sum = float('-inf')
 current_sum =0 for num in nums:
 current_sum = max(num, current_sum + num)
 max_sum = max(max_sum, current_sum)
 return max_sum# 测试用例print(max_subarray_sum([-2, -3,4, -1, -2,1,5, -3])) #7

###3.2 最小生成树#### 题目描述给定一个带权图，找出其中最小的生成树。

#### 输入输出格式输入: 带权图（邻接矩阵）
输出: 最小生成树（列表）

#### 示例代码

import networkx as nxdef min_spanning_tree(graph):
 """
 找出带权图中最小的生成树。
 :param graph: 带权图（邻接矩阵）
 :return: 最小生成树