题目链接 PEEK61 【模板】静态区间最值 题目描述 给定一个长度为  的静态数组 。有  次查询，每次查询给定一个区间 ，要求回答该区间的最大值或最小值。 解题思路 本题是静态区间最值查询（Range Minimum/Maximum Query, RMQ）的模板题。由于数组内容不会改变，且查询次数较多，我们需要一个比每次都遍历区间更高效的数据结构。 解决此问题的经典高效算法是 稀疏表（Sparse Table, ST）。该算法的核心思想是利用动态规划和倍增的思想，预处理出所有长度为  的区间的最大值和最小值，从而实现  的查询。   预处理 ()  我们创建两个二维数组，st_min[p]...

题目链接 PEEK60 旺仔哥哥的约会 题目描述 给定一个由  个节点构成的树形结构。有  次询问，每次询问给定四个节点 。你需要判断从  到  的最短路径，与从  到  的最短路径，是否在树上存在公共节点。 解题思路 在树中，任意两点之间的最短路径是唯一的。因此，问题就是判断 path(a, b) 和 path(c, d) 这两条唯一路径是否相交。 对每次查询都遍历路径并检查交点，效率太低。我们可以利用最近公共祖先（LCA） 的性质来设计一个高效的算法。 核心判定条件 两条路径 path(a, b) 和 path(c, d) 相交的充要条件是：其中一条路径的LCA，在另一条路径上。  令 l...

题目链接 PEEK59 机房传信 题目描述 给定一个由  个节点构成的树形网络。每个节点  转发信息会产生一个延迟，延迟时间等于该节点的度数（即与之直接相连的边的数量）。信息在两点  之间的传递时间，定义为  之间唯一路径上所有节点（包括  和 ）的延迟时间之和。 你需要处理  次独立的查询，每次给定两个节点  和 ，求出它们之间的信息传递最短时间。 解题思路 由于网络是树形结构，任意两点  之间的路径是唯一的，因此“最短时间”就是这条唯一路径上的权值（延迟）之和。节点  的权值等于其度数 deg[i]。 对每次查询都进行一次 DFS/BFS 来寻找路径并求和，时间复杂度为 ，会超时。这是一个...

题目链接 PEEK58 【模板】最近公共祖先（LCA） 题目描述 给定一棵由  个节点组成的、以  为根的多叉树。有  次询问，每次给定两个节点  和 ，你需要求出这两个节点的最近公共祖先（LCA）。 最近公共祖先（LCA）：指在树中离两个节点最近的、且同时是这两个节点的祖先的节点。 解题思路 本题是最近公共祖先（LCA）的模板题。由于节点和查询数量都很大，对于每次查询，从一个节点暴力向上走到根，并记录路径，再从另一个节点向上走直到碰到已记录路径的节点，这种朴素算法的时间复杂度为 ，会超时。 解决此问题的标准高效算法是倍增法（Binary Lifting）。该算法分为预处理和查询两个阶段。  ...

题目链接 PEEK56 数列 k 重排 题目描述 给定一个长度为  的序列  和一个长度为  的置换序列 。我们定义一次操作为：根据  生成一个新的序列 ，其中 。然后用序列  替换原来的序列 。 你需要计算出，对初始序列  执行  次这样的操作后，最终得到的序列是什么。 解题思路 由于操作次数  的值可能非常大（高达 ），直接模拟是不可行的。 该问题的核心是理解操作的本质。k 次操作后，最终序列在 i 位置的值，来自于初始序列的哪个位置？  1 次操作后: A_1[i] = A_0[X[i]] 2 次操作后: A_2[i] = A_1[X[i]]。将 i 替换为 X[i] 代入上式，得到 A...

题目链接 PEEK55 星球传送 题目描述 在一个包含  个星球的游戏中，每个星球  都有一个单向传送门，通往星球 （目标星球可能是自身）。你需要处理  个独立的查询，每个查询给定一个起始星球  和一个传送次数 。你需要计算出，从星球  出发，连续经过  次传送后，最终会到达哪个星球。 解题思路 由于传送次数  的值可能非常大（高达 ），对每次查询都进行  次模拟跳转是不可行的，会导致超时。 这个问题可以被看作是在一个功能图（functional graph，每个节点有且仅有一个出度）上寻找一个节点经过  步后到达的后继节点。这是一个可以使用倍增（Binary Lifting） 算法解决的经典...

题目链接 PEEK52 铁盘整理 题目描述 给定一个包含  () 个不同半径的铁盘的序列，初始时它们是无序堆叠的。我们定义一种操作为“翻转”，即将最上面的  个铁盘（）作为一个整体进行上下翻转。目标是找到一个操作序列，使得所有铁盘从上到下按半径从小到大有序排列，并要求这个操作序列的长度（即翻转次数）最短。 解题思路 这个问题是经典的“煎饼排序”（Pancake Sorting）问题，寻找最少翻转次数是一个 NP-hard 问题。对于  这样的数据规模，常规的广度优先搜索（BFS）因状态空间过大（ 级别）而会导致超时。 正确的做法是使用 迭代加深 A* (Iterative Deepening ...

题目链接 环形字符串跃迁 题目描述 有一个长度为  的环形字符串 。初始时光标位于第  个字符。接下来进行  次移动，每次移动的规则如下： 假设当前光标在第  个位置，向后观察  个字符（不包括当前字符）。  如果在观察的  个字符中存在字符 '0'，则光标移动到其中最远的一个 '0' 的位置。 如果观察范围内没有 '0'，则光标移动到下一个字符的位置，即 。  需要回答  次独立的询问，每次给定不同的  和 ，求出最终光标停留的位置。 解题思路 由于移动次数  的值很大，对每次查询都进行模拟是不可行的。注意到从任意位置开始的下一次移动位置是固定的，这构成了一个功能图（functional g...

题目链接 https://www.nowcoder.com/practice/80fe9a87ed034b70b23b029c5bab6d21 题目描述 在一个  的棋盘上，有若干个白马（用 1 表示）、黑马（用 0 表示）以及一个空格（用 * 表示）。马的移动遵循中国象棋的 “日” 字规则（无 “蹩马腿” 限制），即可以移动到8个可能的方向。给定一个初始棋盘布局，要求计算出最少需要多少步才能移动到如下所示的目标状态。 目标状态： 11111 01111 00*11 00001 00000  如果能在 15 步以内（含 15 步）到达，则输出最少步数；否则输出 -1。 解题思路 这是一个典型的...

题目链接 遥控无人机 题目描述 初始时，无人机位于原点 ，目标是到达点 。给定  条指令，每条指令包含一个位移向量 。对于所有可能的 ，需要计算出有多少种方法，可以从  条指令中恰好选择  条，使得执行后无人机正好到达目标点。 解题思路 本题要求我们对每个可能的指令数量 ，找出选择  条指令使得位移总和为  的方案数。这是一个典型的组合计数问题，与子集和问题相关。 暴力方法与DP的局限性 一个朴素的想法是检查所有  个子集，但这对于  来说太慢了。 另一个思路是动态规划。我们可以定义一个状态 dp[i][j][x][y] 表示从前  条指令中选择  条，使得总位移为  的方案数。然而，位移坐标...

题目链接 八数码 题目描述 在一个 3x3 的方格中，有数字1到8和'x'（代表空格）共九个元素。每次操作可以将空格'x'与其上下左右相邻的数字进行交换。给定一个初始状态，你需要找出将其恢复为目标状态 12345678x 所需的最少交换次数。 解题思路   问题建模：状态图搜索 我们可以将八数碼的每一种可能的排列看作一个状态，每次交换操作看作是状态之间的转移。这样，整个问题就转化为了在一个巨大的状态图中，寻找从初始状态到目标状态的最短路径。 求解无权图的最短路径问题，最经典的算法就是广度优先搜索 (BFS)。   朴素 BFS 一个直接的想法是从初始状态开始进行 BFS。  状态表示：用一个长...

题目链接 模意义下最大子序列和（Hard Version） 题目描述 给定一个包含  个正整数的数组和一个模数 。你需要从数组中选择一个子序列（可以是空序列），使得子序列中所有元素的和对  取模后的结果最大。 解题思路   问题分析与暴力解法 我们需要找到一个子序列，其和 sum 使得 sum % m 最大。 一个朴素的想法是枚举所有可能的子序列。一个长度为  的数组共有  个子序列。对于每个子序列，我们计算其和并取模，然后更新最大值。当  较大时（如此题中的 ）， 是一个天文数字，暴力枚举会严重超时。   折半搜索 (Meet-in-the-Middle) 当问题规模  在40左右，使得  ...

题目链接 填字母游戏 题目描述 在一个一维的格子条上，Alice 和 Bob 轮流填入字母 'L' 或 'O'。第一个成功构成连续子串 "LOL" 的玩家立即获胜。如果所有格子都填满仍未出现 "LOL"，则为平局。 给定一个包含 'L', 'O', '*' (空格) 的初始局面，你需要判断在 Alice 先手且双方都采取最优策略的情况下，最终的游戏结果。 解题思路 这是一个典型的组合游戏，其核心是找到最优策略。我们可以通过递归搜索所有可能的游戏进程，并用记忆化来优化，这本质上是一种动态规划（记忆化搜索）。 1. 状态定义 游戏中的任何一个局面都可以用一个...

题目链接 拼接木棍 题目描述 给定  根小木棍的长度，这些小木棍是由若干根等长的大木棍截断而来的。你需要找出这些大木棍原始的、最小的可能长度。 解题思路   问题转化与搜索空间 这个问题可以转化为一个搜索问题：我们尝试每一种可能的“原始长度” ，然后验证是否能用所有小木棍恰好拼接成若干根长度为  的大木棍。我们要求的，就是能满足条件的最小的 。  的可能取值范围是什么？  下界： 必须至少等于最长的那根小木棍的长度。 上界：在最极端的情况下，所有小木棍都来自同一根大木棍，所以  不会超过所有小木棍的总长度。 约束：所有小木棍的总长度 total_sum 必须能被  整除。  因此，我们的整体算...