### 第15届蓝桥杯Python B组真题解析 #### 题目概述 第十五届蓝桥杯 Python B 组省赛共设有八道题目，相比往年的十道有所减少。整体难度也较往年有所降低[^1]。 #### 示例题目：穿越时空之门 对于特定的竞赛题目如“穿越时空之门”，虽然具体的解答过程未在此提供，但可以推测这类问题通常涉及算法设计与优化。解决此类问题的关键在于理解时间旅行的概念以及如何通过编程实现有效的路径规划或状态转换逻辑。 #### 岛屿连接问题详解 针对给出的具体实例——岛屿间的合并与撤销操作： - **输入描述** - 输入的第一行为整数 n (0 ≤ n ≤ 1e5)，表示岛屿的数量。 - 接下来若干行每行的第一个整数 op 表示一种操作类型： - 若 op=1，则接下来有两个正整数 a 和 b(1≤a,b≤n)，代表要建立一座桥梁连接岛屿 a 和 b； - 若 op=2，则意味着移除最后创建的一座桥； - 若 op=3，则询问给定编号为 a 和 b 的两个岛屿之间是否存在直接或间接的道路相连；此时仅需读入这两个参数即可完成判断。 - 当遇到不等于 1, 2 或者 3 的其他数值时停止处理数据流。 - **解决方案思路** 使用并查集（Union-Find Set）来高效管理这些动态变化的关系网络是一个不错的选择。该结构允许快速执行如下两种基本操作： - `union(x,y)`：将包含元素 x 和 y 的集合合并成一个新的集合。 - `find(x)` ：查找某个节点所属的根节点，从而确定它属于哪个连通分量。 下面是一份基于上述原理编写的 Python 实现方案： ```python class UnionFind: def __init__(self, size): self.parent = list(range(size)) def find(self, p): if self.parent[p] != p: self.parent[p] = self.find(self.parent[p]) # 路径压缩 return self.parent[p] def union(self, p, q): rootP = self.find(p) rootQ = self.find(q) if rootP == rootQ: return False self.parent[rootP] = rootQ return True def process_islands(n, operations): uf = UnionFind(n + 1) # 初始化并查集对象 history = [] # 记录每次成功的联合动作以便回溯取消 results = [] for operation in operations: cmd, *args = map(int, operation.split()) if cmd == 1 and len(args)==2: # 处理联合作业 success = uf.union(*args) if success: history.append(tuple(args)) # 成功才记录历史 elif cmd == 2 and history: # 执行撤消命令 last_unioned_pair = history.pop() uf.undo(last_unioned_pair) elif cmd == 3 and len(args)==2: # 查询两点间是否有路可达 result = 'Yes' if uf.find(args[0])==uf.find(args[1]) else 'No' results.append(result) return "\n".join(results) # 测试用例模拟器 if __name__=='__main__': sample_input=""" 7 1 1 2 1 2 3 3 1 3 2 3 1 3""" lines=[line.strip()for line in sample_input.strip().split('\n')] print(process_islands(int(lines[0]),lines[1:])) ``` 此代码片段展示了如何利用并查集有效地管理和追踪多个实体之间的关系变动情况，并能够响应不同类型的查询请求。值得注意的是，在实际比赛中可能还需要考虑更多边界条件和其他特殊情况下的鲁棒性增强措施[^2]。