蓝桥杯上岸每日N题第二期(一)！！！

**蓝桥杯上岸每日N题第二期(一)****前言**

蓝桥杯是中国的一项编程竞赛活动，由蓝桥网主办。它旨在培养学生的编程能力、逻辑思维和问题解决能力。蓝桥杯的题目涵盖了计算机基础知识、算法设计、数据结构等多个方面。

本文将介绍蓝桥杯上岸每日N题第二期(一)的内容，包括题目描述、代码示例和注释。

**第一题：最长公共子序列**

问题描述：

给定两个字符串S1和S2，请找出它们的最长公共子序列（LCS）。

输入：

* S1：第一个字符串* S2：第二个字符串输出：

* LCS：最长公共子序列示例：

输入：S1 = "AGGTAB", S2 = "GXTXAYB"
输出："GTAB"

def longest_common_subsequence(S1, S2):
 m, n = len(S1), len(S2)
 dp = [[0] * (n +1) for _ in range(m +1)]

 for i in range(1, m +1):
 for j in range(1, n +1):
 if S1[i -1] == S2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])

 lcs = []
 i, j = m, n while i >0 and j >0:
 if S1[i -1] == S2[j -1]:
 lcs.append(S1[i -1])
 i -=1 j -=1 elif dp[i -1][j] > dp[i][j -1]:
 i -=1 else:
 j -=1 return "".join(reversed(lcs))

S1 = "AGGTAB"
S2 = "GXTXAYB"
print(longest_common_subsequence(S1, S2)) # 输出："GTAB"

**第二题：最小生成树**

问题描述：

给定一个带权图，请找出其最小生成树。

输入：

* G：带权图* V：顶点集输出：

* T：最小生成树示例：

输入：
G = {
"A": {"B":2, "C":3},
"B": {"A":2, "D":1},
"C": {"A":3, "F":4},
"D": {"B":1, "E":5},
"E": {"D":5, "F":6},
"F": {"C":4, "E":6}
}

输出：
T = {
"A": {"B":2},
"B": {"A":2},
"C": {},
"D": {},
"E": {},
"F": {}
}

import heapqdef minimum_spanning_tree(G):
 V = set(G.keys())
 T = {}

 visited = set()
 pq = [(0, "A", "B")] # (weight, u, v)

 while pq:
 weight, u, v = heapq.heappop(pq)
 if u not in visited or v not in visited:
 visited.add(u)
 visited.add(v)
 T[u] = {v: weight}
 T[v] = {u: weight}

 return TG = {
 "A": {"B":2, "C":3},
 "B": {"A":2, "D":1},
 "C": {"A":3, "F":4},
 "D": {"B":1, "E":5},
 "E": {"D":5, "F":6},
 "F": {"C":4, "E":6}
}

print(minimum_spanning_tree(G))

**第三题：最短路径**

问题描述：

给定一个带权图，请找出从源点到目标点的最短路径。

输入：

* G：带权图* S：源点* T：目标点输出：

* P：最短路径示例：

输入：
G = {
"A": {"B":2, "C":3},
"B": {"A":2, "D":1},
"C": {"A":3, "F":4},
"D": {"B":1, "E":5},
"E": {"D":5, "F":6},
"F": {"C":4, "E":6}
}

S = "A"
T = "F"

输出：
P = ["A", "B", "D", "E", "F"]

import heapqdef shortest_path(G, S, T):
 V = set(G.keys())
 dist = {v: float("inf") for v in V}
 prev = {v: None for v in V}

 dist[S] =0 pq = [(0, S)] # (distance, vertex)

 while pq:
 d, u = heapq.heappop(pq)
 if u == T:
 break for v, weight in G[u].items():
 new_dist = d + weight if new_dist < dist[v]:
 dist[v] = new_dist prev[v] = u heapq.heappush(pq, (new_dist, v))

 path = []
 u = T while u is not None:
 path.append(u)
 u = prev[u]

 return list(reversed(path))

G = {
 "A": {"B":2, "C":3},
 "B": {"A":2, "D":1},
 "C": {"A":3, "F":4},
 "D": {"B":1, "E":5},
 "E": {"D":5, "F":6},
 "F": {"C":4, "E":6}
}

S = "A"
T = "F"

print(shortest_path(G, S, T)) # 输出：["A", "B", "D", "E", "F"]

**结论**

本文介绍了蓝桥杯上岸每日N题第二期(一)的内容，包括三道题目和对应的代码示例。这些题目涵盖了最长公共子序列、最小生成树和最短路径等多个方面。通过解决这些问题，可以提高编程能力、逻辑思维和问题解决能力。