题目链接 上司的舞会 题目描述 公司有  名员工，构成一个多棵树组成的森林结构（即层级关系）。每位员工要么是最高层（没有上司），要么有且仅有一位直接上司。需要将所有员工分到若干小组，要求同一个小组内的任意两名员工之间不能有直接或间接的上级关系。求满足该条件的最小小组数量。 解题思路 这道题的核心在于理解分组的约束条件。 核心约束 “同一小组内不得出现任何一对员工具有上级关系。” 这句话是解题的关键。让我们考虑一条从上到下的指挥链，例如：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 的核心思想是“一条路走到黑”，即从起点开始，沿着一个方向不断探索，直到到达终点或遇到死路（墙壁或已访问过的格子）。如果遇到死路...

题目链接 挡住洪水 题目描述 给定一个  的地图，其中 . 代表洪水区域，# 代表空地。四连通的 # 组成一个独立的空地区域。在一天后，所有与洪水区域 . 相邻（上下左右）的空地 # 都会被洪水淹没。 任务是计算一天后，有多少个独立的空地区域会被完全淹没。 解题思路 本题的目标是统计被完全淹没的空地区域数量。我们首先需要明确一个区域被“完全淹没”的条件。 根据题意，一个空地格子 '#' 如果与任意一个洪水格子 '.' 相邻，那么它在一天后就会被淹没。因此，一个由多个 '#' 组成的区域会被完全淹没，当且仅当该区域内的每一个 '#' 格子都至少与一个 '.' 格子相邻。 反向思考，一个区域不会被...

题目链接 小A的线段（easy version） 题目描述 在坐标轴的整数点  上给出  条闭区间线段，第  条线段用其端点  描述。 现在要从这  条线段中选择若干条，使得每个整数点被至少两条所选线段覆盖。求满足条件的选择方案数量。 两种方案视为不同，当且仅当存在某条线段在两方案中的“选不选”状态不同。答案对  取模。 解题思路 本题要求我们从  条线段中选出若干条，使得  中的每个整数点都被至少两条线段覆盖，并计算满足条件的方案总数。 这是一个组合计数问题。由于  的范围通常不大（例如 ），我们可以考虑使用搜索算法来遍历所有可能的线段选择组合。一个朴素的方案是枚举  种选择，然后对每一种选...

题目链接 剪纸游戏 题目描述 在一张由 . 和 * 组成的  网格纸上，. 代表被剪去的小方格，* 代表保留的小方格。被剪下的图案都是由 . 构成的、互相不连通的区域。你需要计算，在所有被剪下来的图案中，有多少个是长方形（正方形被视为特殊的长方形）。 解题思路 这个问题可以分解为两个主要步骤：  找出所有被剪掉的图案：每个图案都是一个由 . 组成的连通块。 判断每个图案的形状：检查每个连通块是否构成一个实心的长方形。  我们可以通过图的遍历算法，如广度优先搜索 (BFS) 或深度优先搜索 (DFS)，来系统地解决这个问题。 算法步骤如下：   遍历网格：  我们使用一个 visited 二维数...