题目链接 图的分类 题目描述 给定一个包含  台计算机和  条网线的连通网络。判断该网络的拓扑结构是链型 (line)、环型 (ring)、星型 (star)，还是不属于以上三类的未知结构 (unknown)。 解题思路 本题的核心是根据图中节点的度数分布来对图进行分类。一个节点的“度”是指与该节点直接相连的边的数量。由于题目保证图是连通的，我们可以通过统计所有节点的度数，来总结出每种特定结构的独有特征。 1. 结构特征分析   链型 (line):   一条链有  个节点，必然有  条边。   度数分布：恰好有两个度为  的节点（链的两端），以及  个度为  的节点（链的中间部分）。    ...

题目链接 小红的树上游戏 题目描述 在一棵  个节点的无根树上，小红和朋友轮流删除叶子节点。若某位玩家删除了一个特殊的节点 ，则该玩家立即获胜。双方都采取最优策略，小红先手，判断她是否必胜。 解题思路 本题是一个博弈问题。由于双方都采取最优策略，我们需要找到决定游戏胜负的根本性质。 1. 直接获胜条件 游戏最简单的情况是，特殊节点  在游戏开始时就是一个叶子节点（度数为），或者是一个孤立点（度数为，当  时）。在这种情况下，小红作为先手，可以在她的第一个回合直接删除节点  并获胜。因此，这是一个必胜条件。 2. 游戏过程分析 如果节点  的初始度数大于，游戏将继续。双方轮流移除叶子节点。   ...

题目链接 先序遍历、中序遍历和后序遍历 题目描述 给定一棵包含  个节点的二叉树，以  条有向边 （父节点指向子节点）的形式给出。子节点的左右关系需要根据以下规则确定：   若父节点有两个孩子，编号较小者为左孩子，较大者为右孩子。   若父节点只有一个孩子：  若子节点编号大于父节点编号，则该孩子为左孩子。 否则（子节点编号小于父节点编号），该孩子为右孩子。    你需要输出该二叉树的先序、中序、后序遍历序列。 解题思路 本题的解法分为两个主要步骤：1. 重建二叉树结构 和 2. 执行标准遍历。 1. 重建二叉树 首先，我们需要根据输入的父子关系和给定的左右孩子规则，构建出完整的二叉树。   ...

题目链接 上司的舞会 题目描述 公司有  名员工，构成一个多棵树组成的森林结构（即层级关系）。每位员工要么是最高层（没有上司），要么有且仅有一位直接上司。需要将所有员工分到若干小组，要求同一个小组内的任意两名员工之间不能有直接或间接的上级关系。求满足该条件的最小小组数量。 解题思路 这道题的核心在于理解分组的约束条件。 核心约束 “同一小组内不得出现任何一对员工具有上级关系。” 这句话是解题的关键。让我们考虑一条从上到下的指挥链，例如：A 是 B 的上司，B 是 C 的上司。  A 和 B 不能在同一组。 B 和 C 不能在同一组。 A 和 C也不能在同一组（因为 A 是 C 的间接上司）。 ...

题目链接 求树的根 题目描述 给定一棵包含  个节点的有根树，节点编号从 1 到 。输入以  条有向边 u -> v 的形式给出。你需要找出并输出：  树的根节点编号。 所有叶子节点的编号，并按升序排列。  解题思路 这道题的本质是利用图论中节点度 (degree) 的概念来识别树的特定部分。题目以有向边的形式给出了树的结构，这为我们提供了清晰的方向。 核心定义  入度 (In-degree)：指向一个节点的边的数量。 出度 (Out-degree)：从一个节点出发的边的数量。  根据有根树的性质，我们可以得出以下结论：  根节点：是树的唯一源头，没有其他节点指向它。因此，根节点的入度为...

题目链接 【模板】链式前向星 题目描述 给定一个包含  个点、 条边的无向图。点的编号从 1 到 。你需要对于每个点，升序输出其所有直接相连的点的编号。如果一个点没有任何邻居，则输出 "None"。 解题思路 本题的本质是图的存储与遍历。我们需要一种数据结构来表示图，然后遍历这个结构来找到每个点的所有邻居。 在 C++ 中，最直接的方法是使用 std::vector<std::vector<int>> adj，其中 adj[i] 存储了节点  的所有邻居。然而，在传统的算法竞赛中，链式前向星是一种更常用、空间效率更高、且在某些情况下遍历速度更快的静态...

题目链接 小红的皇后 题目描述 在一个  的棋盘上，有一些格子是障碍物(*)，其余为空格(.)。一个皇后从左上角  出发，目标是到达右下角 。皇后每次移动可以沿右、下、右下三个方向之一前进任意多格，且移动路径上不能有障碍物。求从起点到终点的最少移动步数。 解题思路 本题可以看作一个最短路径问题，但由于边的权重特殊（每次移动，无论多远，成本都是1），使用动态规划是解决此类问题的经典方法。 核心思想 问题的核心在于，沿同一个方向连续移动不增加步数，但转换方向则需要增加一步。这启发我们，DP的状态不仅要记录位置，还必须记录是“通过哪种方向的移动”到达该位置的。 动态规划设计   状态定义:  表示到...

题目链接 太阳系DISCO 题目描述 在一个由  个行星构成的环形星系中，行星顺时针编号为  到 （ 为偶数）。你从起点行星  出发，目标是到达终点行星 。你有以下三种移动方式，每种都消耗 1 单位时间：  顺时针移动  颗行星。 逆时针移动  颗行星。 传送：顺时针移动  颗行星（即跳到正对面）。此技能最多使用  次。  请求出从  到  的最少时间。如果无法到达，输出 -1。 解题思路 这是一个在带有资源限制（传送次数）的图上求最短路径的问题。由于每次操作的成本都是 1，广度优先搜索 (BFS) 是最合适的算法。 核心思想：双层图模型 问题的关键在于如何处理传送技能和其次数限制。一个传送操...

题目链接 时津风的资源收集 题目描述 玩家有四种资源，初始值均为 10。给定四种资源的目标量 。玩家可以对任意一种资源执行以下操作，但必须保证资源量始终在  的区间内：  资源量 。 资源量 。 资源量 。 直接将资源量设为上限 。 直接将资源量设为下限 。  每种操作计为一次。求使四种资源量同时达到目标值所需的最少总操作次数。 解题思路 本题的核心是计算将四种资源从初始值 10 变为目标值所需的最少操作次数。由于对每种资源的操作是相互独立的，我们可以将问题分解为四个相同的子问题：计算单一资源从 10 变为目标值  所需的最少操作次数。最终答案是这四个子问题解的和。 对于单一资源，问题可以抽象...

题目链接 双人成行 题目描述 在一个  的网格迷宫中，有平地(.)、陷阱(#)和传送门(@)。你和另一个你（记为玩家1和玩家2）同时从起点  出发。 游戏分为两个阶段：  联动阶段：你们必须同时行动，且方向相反。例如，玩家1向上移动一格，玩家2必须向下移动一格。此阶段直到其中一人到达传送门时结束。 单人阶段：当一人通过传送门离开后，剩下的一人可以自由地向上下左右移动，直到也到达一个传送门。  在任何时候，任何人都不能移动到边界外或陷阱上。 请求出两人都成功离开迷宫的最短总步数。如果无法做到，输出 -1。 解题思路 这是一个复杂的最短路问题，我们可以将其分解为两个独立的子问题来解决：单人寻路和双...

题目链接 迷宫 题目描述 给定一个  的迷宫，由 # 与 . 两种字符组成。其中 # 代表障碍物，. 表示空地。迷宫中还有一个起点 S 和一个终点 E，它们都可以视为空地。 由于近期迷宫发生了塌方，导致起点和终点之间可能并不连通。幸运的是，你拥有一种超能力——在迷宫中移动时（移动方向为上、下、左、右四个方向之一），可以在当前位置朝任一方向（上、下、左、右四个方向之一）释放激光。激光能够清除该方向上所有的障碍物，并且这种超能力至多只能使用一次。 现在，你需要判断是否能利用这种超能力成功从起点到达终点。 解题思路 本题是一个带有特殊规则的图上寻路问题。问题的关键在于“激光至多使用一次”这个条件。我...

题目链接 走一个大整数迷宫 题目描述 给定一个  的矩阵迷宫。矩阵中第  行  列的格子的权值为 。 LH 从起点  出发，目标是到达出口 。迷宫配有一个计数器，其初始值为起点  的权值 。 LH 每秒必须从当前格子向上下左右四个相邻方向之一移动一格（不得停留或走出迷宫）。假设 LH 从  移动到 ，计数器会累加 。 只有当 LH 身处出口 ，且计数器的总值  恰好满足  时，大门才会打开。 请计算 LH 逃离迷宫所需的最短时间（秒）。如果无论如何都无法逃离，则输出 。 解题思路 本题要求解在满足特定模数条件下，从起点到终点的最短路径。这是一个典型的广度优先搜索 (BFS) 问题，但需要对状态...

题目链接 挡住洪水 题目描述 给定一个  的字符矩阵作为地图，其中 '*' 代表围墙，'0' 代表空地。所有四方向（上下左右）连通的 '0' 构成一个区域。 如果一个区域四周都被围墙或地图边界所包围，那么洪水就无法进入，该区域被视为安全区域。请统计地图中所有安全区域包含的 '0' 单元格的总数。 解题思路 (最终修正版) 本题的真实意图是计算所有不与地图边界连通的 '0' 单元格的总数。一个区域只要有任何一个 '0' 单元格在地图的边界上，那么该区域的所有 '0' 单元格都视为不安全。 正确的解法依然是采用逆向思维：   识别并标记所有不安全的单元格： 首先，遍历地图的所有边界（第一行、最后一...

题目链接 迷宫问题 题目描述 在一个  的网格迷宫中，0 代表通路，1 代表墙壁。起点固定为左上角的 ，终点固定为右下角的 。你需要找到一条从起点到终点的可行路径，并按顺序输出路径上每个格子的坐标。题目保证路径存在且唯一。 解题思路 本题是一个典型的迷宫寻路问题。我们需要在给定的网格中，找到一条从起点  到终点  的可行路径。由于题目保证路径存在且唯一，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。这里我们采用深度优先搜索（DFS）的方法。 DFS 的核心思想是“一条路走到黑”，即从起点开始，沿着一个方向不断探索，直到到达终点或遇到死路（墙壁或已访问过的格子）。如果遇到死路...