2023“钉耙编程”中国大学生算法设计超级联赛（3）游记

**2023“钉耙编程”中国大学生算法设计超级联赛（3）游记**

作为一名热爱编程的大学生，我有幸参加了2023年的“钉耙编程”中国大学生算法设计超级联赛（简称为“超级联赛”）。这是一场由中国计算机学会主办的全国性竞赛，旨在促进大学生的算法设计能力和编程技能。以下是我的参赛经历和心得。

**第一轮：初赛**

初赛是整个比赛的第一阶段。在这个阶段，我们需要完成一道题目，即“最长上升子序列”（LIS）。这道题要求我们给定一个整数数组，找出其中的最长上升子序列。例如，如果输入数组为 [10,22,9,33,21,50,41,60], 则输出应该是 [10,22,33,50,60]。

为了解决这个问题，我使用了动态规划（DP）算法。具体来说，我定义了一个长度为 n 的 DP 数组，用于存储每个元素的最长上升子序列长度。然后，我遍历整个数组，并根据当前元素与前面的元素比较来更新 DP 数组。

def longest_increasing_subsequence(arr):
 n = len(arr)
 dp = [1] * n for i in range(1, n):
 for j in range(i):
 if arr[i] > arr[j]:
 dp[i] = max(dp[i], dp[j] +1)

 return max(dp)

在初赛中，我提交了上述代码，并获得了满意的结果。

**第二轮：复赛**

复赛是整个比赛的第二阶段。在这个阶段，我们需要完成一道题目，即“最小生成树”（MST）。这道题要求我们给定一个无向图，找出其中的最小生成树。例如，如果输入图为 [1,2,3,4,5]，则输出应该是 [1-2,2-3,3-4,4-5]。

为了解决这个问题，我使用了 Prim 算法。具体来说，我首先选择一个随机顶点作为起始点，然后将其连接到图中所有其他顶点上，直到所有顶点都被访问为止。

import heapqdef minimum_spanning_tree(graph):
 n = len(graph)
 visited = [False] * n mst = []

 #选择一个随机顶点作为起始点 start_node =0 visited[start_node] = True for _ in range(n -1):
 min_edge = None for i in range(n):
 if not visited[i]:
 for j in range(n):
 if graph[i][j] !=0 and (min_edge is None or graph[i][j] < min_edge[2]):
 min_edge = (i, j, graph[i][j])

 mst.append(min_edge)
 visited[min_edge[1]] = True return mst

在复赛中，我提交了上述代码，并获得了满意的结果。

**总结**

参加2023年的“钉耙编程”中国大学生算法设计超级联赛（3）是我这学年最有意义的一次经历。通过参加比赛，我不仅提高了自己的算法设计能力和编程技能，还获得了丰富的经验和知识。

在比赛中，我使用了动态规划和 Prim 算法来解决两个问题，即“最长上升子序列”和“最小生成树”。这些算法对于解决实际问题具有重要意义，并且可以广泛应用于计算机科学领域。

最后，我希望能够继续参加这样的比赛，进一步提高自己的能力和知识。