题目链接 数楼梯 题目描述 给定一段有  阶的楼梯，你每一步可以选择上  阶或者  阶。求从楼梯底端走到顶端共有多少种不同的走法。由于答案可能很大，请将结果对 998244353 取模后输出。 解题思路 这是一个经典的动态规划问题。 我们定义  为到达第  阶楼梯的不同走法数量。 要想到达第  阶楼梯，最后一步只可能是从第  阶或第  阶上来的：  从第  阶走  阶上来，这种情况的走法数量等于到达第  阶的走法数量，即 。 从第  阶走  阶上来，这种情况的走法数量等于到达第  阶的走法数量，即 。  因此，可以得到状态转移方程：  接下来确定初始状态（边界条件）：  对于第  阶楼梯，只有...

题目链接 硬币凑钱 题目描述 银行拥有面值为1元、5元与7元的硬币若干，每种面值的硬币数量均视为无限。现在需要支付恰好  元，求出所需硬币数量的最小值。 解题思路 这是一个典型的“完全背包”求最优解的问题。我们可以使用动态规划来求解。 我们定义一个一维数组 ，其中  表示凑成总金额为  所需的最少硬币数量。我们的目标是求 。 首先，初始化  数组。，因为凑成金额0需要0个硬币。对于其他金额 ，我们应该将  初始化为一个非常大的数（表示无穷大），代表当前还无法凑成该金额。 然后，我们遍历每一种硬币。对于面值为  的硬币（这里是1, 5, 7），我们来更新  数组。对于一个金额 （从  到 ），凑...

题目链接 小红的01串 题目描述 给定一个由  个非负整数组成的数组。一轮操作定义为：首先计算数组的 （未在数组中出现的最小非负整数），然后将数组中的每个数  更新为 。求至少需要多少轮操作才能使数组中的每个数都相同。如果不可能，则输出 -1。 解题思路 本题要求计算最少需要多少轮操作才能使数组中的所有元素都相同。直接模拟操作在数组规模和数值范围较大时会超时，因此我们需要找到一个数学规律来直接计算答案。 首先，我们处理几个基本情况：  初始状态已满足：如果数组中的所有元素在开始时就已经相同，那么所需的操作轮数就是 0。 不可能完成：如果数组元素不相同，那么唯一可能达成的相同状态就是所有元素都变...

题目链接 斐波那契字符串 题目描述 一个由 '0' 和 '1' 构成的斐波那契字符串  定义如下：     （"+" 表示字符串拼接）  求  中逆序对（即子序列 "10"）的数量，答案对  取模。 解题思路 本题要求计算特定规则生成的斐波那契字符串  中 "10" 子序列的数量。由于  的值可能很大，我们无法直接构造字符串，必须通过递推关系来解决。 令  表示  中 "10" 子序列的数量。 令  表示  中字符 '0' 的数量。 令  表示  中字符 '1' 的数量。 根据定义 ，我们可以分析  中逆序对的来源...

题目链接 卡牌游戏 题目描述 有  张卡牌排成一行，每张卡牌有分值 。每次操作可以选择最左端的连续若干张（至少一张）卡牌，将它们替换为一张新卡牌，新卡牌的分值为被替换卡牌的分值之和。每次操作后，新卡牌的分值会累加到总分中。求能够获得的最高总分。 解题思路 这是一个典型的动态规划问题。经过用户的指正，先前版本对题目规则的理解有误。核心规则是**“每次操作，旺仔哥哥可以选取位于序列最左端的连续若干张卡牌（不少于2张）”**。 基于这个关键点，我们重新设计DP方案： 令  为对前  张卡牌（即 a[0] 到 a[i-1]）进行一系列操作，最终合并为一张牌时，所能获得的最大总分。 同时，令  为原序列...

题目链接 染色 题目描述 有  罐油漆，进行  次操作。每次操作将一个区间  内的所有油漆罐加入一种颜色（1-黄, 2-蓝, 3-红）。一种油漆罐的最终颜色由其包含的颜料集合决定。求所有操作结束后，最终颜色为绿色（恰好包含黄色和蓝色，不包含红色）的油漆罐数量。 解题思路 本题的本质是需要对多个区间进行更新操作，并最终查询每个位置的状态。由于涉及三种独立的颜色，我们可以将问题分解，分别追踪每一罐油漆是否含有黄、蓝、红三种颜料。 这是一个典型的区间更新问题。如果对每次操作都遍历区间  来更新状态，总时间复杂度会是 ，在数据量较大时可能会超时。 更高效的方法是使用差分数组。因为三种颜料的添加是独立事...

题目链接 空间跃迁 题目描述 有  个城市排成一列，从城市  到城市  的耗时为 。可以从 1 号城市出发到  号城市，途中可以使用一次空间跃迁。空间跃迁的半径为 ，即可以从第  个城市无时间消耗地传送到第  或第  个城市。求从 1 号城市到  号城市的最小总耗时。 解题思路 本题的目标是找到一条从城市 1 到城市  的路径，该路径包含一次空间跃迁，使得总耗时最小。 我们可以将整个行程分为三段：  从城市 1 走到城市 。 从城市  空间跃迁到城市 （其中  或 ）。 从城市  走到城市 。  总耗时 = (从 1 到  的耗时) + (从  到  的耗时)。空间跃迁本身不耗时。 为了快速计...

题目链接 【模板】二维差分 题目描述 给定一个  行  列的初始矩阵，进行  次操作。每次操作将指定的子矩阵中每个元素的值加上一个给定的整数 。所有操作完成后，输出最终的矩阵。 解题思路 本题要求对矩阵的子区域进行频繁的增减操作，这是二维差分算法的典型应用场景。 如果直接对每次操作都遍历子矩阵进行更新，时间复杂度为 ，在数据量较大时会超时。使用二维差分可以将每次子矩阵的更新操作优化到  的时间复杂度。 二维差分的核心是构建一个差分矩阵 。对原矩阵  进行区间  到  增加值  的操作，等价于在差分矩阵  上进行以下四个点的修改：   增加 ：表示从  开始的所有元素都增加了 。  减少 ：为了...

题目链接 【模板】二维前缀和 题目描述 给定一个  行  列的矩阵，有  次查询，每次查询给定一个子矩阵的左上角坐标  和右下角坐标 ，求该子矩阵中所有元素的和。 解题思路 本题是典型的二维区间求和问题，可以使用二维前缀和的方法高效解决。 一维前缀和是求解序列中任意区间和的有效方法，其核心思想是预处理一个前缀和数组 ，其中  记录了序列前  个元素的和。这样，区间  的和就可以通过  在  的时间内计算出来。 二维前缀和是一维前缀和思想在二维矩阵上的扩展。我们同样可以预处理一个二维前缀和矩阵 ，其中  记录了以  为左上角， 为右下角的子矩阵中所有元素的和。  的递推计算公式为：  其中， 是...

题目链接 植树节 题目描述 一排从 0 开始无限延伸的树苗，有  名志愿者。第  名志愿者会对闭区间  内的每一棵树苗浇一次水。求所有志愿者完成后，被浇水次数最多的树苗被浇了多少次水。 解题思路 本题要求的是多个区间覆盖后，单个点的最大覆盖次数。 我们可以想象一个记录每棵树被浇水次数的数组 counts。每名志愿者对区间  进行浇水，就相当于将 counts 数组在  区间内的所有值都加 1。在所有志愿者操作完后，我们需要求 counts 数组中的最大值。 如果对每个志愿者的区间都进行一次遍历更新，当区间很大、志愿者很多时，总时间复杂度会非常高，导致超时。 这是一个典型的区间批量修改问题，可以...

题目链接 舞萌时间到！ 题目描述 给定一个由 'P', 'p', 'G', 'g', 'm' 组成的判定序列字符串，分别对应 dx 分 3, 2, 1, 0, -1。现有  次询问，每次给出一个区间 ，求此区间内 dx 分的总和。 解题思路 本题的核心是求一个固定序列在多个不同区间的“分值之和”。这是一个典型的静态区间和问题，与 BGN51 的问题模型完全一致。最高效的解法是使用前缀和。 首先，我们需要将输入的判定字符串转换为一个分值数组。我们可以建立一个映射关系：  'P' -> 3 'p' -> 2 'G' -> 1 'g' -> 0 'm' -> 0  然后...

题目链接 牛牛与切割机 题目描述 给定一个长度为  的序列 。将这个序列切割一刀，划分为两个非空的子序列。切割的代价定义为两个子序列元素和的乘积。求最小的切割代价。 解题思路 本题要求找到一个切割点，使得左右两边子序列元素和的乘积最小。 假设我们在第  个元素之后进行切割（）。  左边的子序列是 。 右边的子序列是 。  设左边子序列的和为 。 设右边子序列的和为 。 那么，在第  个元素后切割的代价就是 。 我们的目标就是找到一个 （从 1 到 ），使得  最小。 一个朴素的想法是，遍历所有可能的切割点  (from 1 to )：  对于每个 ，计算左边和 。 计算右边和 。 计算乘积，并...

题目链接 【模板】差分 题目描述 给定一个长度为  的数组，有  次修改操作，每次操作将指定区间  内的所有元素都加上一个值 。求所有操作完成后的最终数组。 解题思路 本题的核心在于需要对数组进行频繁的区间修改。如果每次修改都遍历  区间，那么  次操作的总时间复杂度将是 ，在  和  都很大的情况下会超时。 为了高效地处理区间修改，我们可以引入差分数组。 什么是差分？ 差分是前缀和的逆运算。对于一个原数组 ，它的差分数组  定义为：  特别地，我们定义 。 从差分数组  反推原数组 ，只需要对  求前缀和即可：  差分如何优化区间修改？ 差分数组最强大的特性在于，对原数组  的一个区间  加...

题目链接 【模板】静态区间和（前缀和） 题目描述 给定一个长度为  的数组，有  次询问，每次询问一个区间  的和。 解题思路 本题是静态区间求和问题，即数组本身不会发生改变。对于这类问题，最经典和高效的算法是前缀和。 前缀和的核心思想是预处理出一个数组，我们称之为前缀和数组 ，其中  记录了原数组从第 1 个元素到第  个元素的累加和。  为了方便计算，我们通常让前缀和数组的下标从 1 开始，并定义 。 这个前缀和数组可以在  的时间内通过一次遍历计算出来，递推公式为：  当我们需要查询任意区间 （下标从 1 开始）的和时，我们可以利用已经计算好的前缀和数组。区间  的和等于 "前...