题目链接 构造数对 题目描述 给定一个正整数 ，请你构造一个由两个正整数  组成的数对，使其同时满足下列全部条件：    整除 （）    若存在多个满足要求的数对，你可以输出其中任意一个；若不存在，则输出 -1。 解题思路 这是一个构造性问题，我们可以尝试寻找一个最简单的构造方案。 题目要求  和  都是不超过  的正整数，一个自然的想法是令  和  都取最大值，即 。我们来验证这个构造是否满足所有条件。  ：当  时，此条件为 。因为题目保证  是正整数，所以 ，该条件恒成立。 ：当  时，此条件为 ，即  能被  整除。对于任意正整数 ，该条件恒成立。 ：当  时，此条件为 ，即 。这个...

题目链接 构造C的歪 题目描述 给定两个整数  和 ，需要找到第三个整数 ，使得这三个数排序后能构成一个等差数列。输出任意一个满足条件的  即可。 解题思路 等差数列的核心性质是中间项是首末两项的平均值。换句话说，如果排序后的三个数为 ，那么必须满足 ，即 。 我们设给定的两个数为  和 ，要找的数为 。不失一般性，我们先对  和  进行排序，得到  和 。现在我们有两个数  和 ，需要找到第三个数  使得它们能构成等差数列。有以下三种可能的情况：   是中间项：数列为 。 此时公差为 ，那么第三个数 。  是中间项：数列为 。 此时公差为 ，那么第一个数 。  是中间项：数列为 。 此时 。...

题目链接 【模板】01背包 题目描述 你有一个最大容量为  的背包和  件物品。第  件物品的体积为 ，价值为 。每件物品只有一件，可以选择放或不放。 题目要求计算两种方案下的最大总价值：  方案A：不要求装满背包。 方案B：要求最终恰好装满背包。如果无法恰好装满，则答案记为 。  解题思路 这是经典的 01背包 问题，可以使用动态规划来解决。由于空间复杂度有要求，我们需要使用一维数组（滚动数组）进行优化。 我们定义  为在背包容量为  的限制下，所能获得的最大价值。我们的目标是求解两种不同要求下的 。 核心状态转移方程： 对于第  件物品（体积 ，价值 ），要更新容量为  的状态 ，我们有两...

题目链接 最大子段和 题目描述 给定一个长度为  的整数数组 。请你从中选取一个非空子数组（连续的一段），使得其元素之和最大。求出该最大和。 解题思路 本题是经典的动态规划问题，通常使用“Kadane算法”来高效解决。 我们定义  为以数组中第  个元素  结尾的连续子数组的最大和。我们的目标是求出所有  中的最大值。 对于第  个元素，以它结尾的最大和子数组有两种可能：  子数组只包含  这一个元素。 子数组是在以  结尾的最大和子数组后面，再接上  形成的。  因此，我们可以得到状态转移方程：  这个方程的含义是：以  结尾的最大子数组和，要么是  本身（这意味着开启一个新的子数组），要么...

题目链接 撞车 题目描述 一条单向单车道的道路上有  辆车，第  辆车位于 ，速度大小为 。为了避免碰撞，可以移除一些车辆。请求出至少需要移除几辆车，才能让剩下的车不发生碰撞。 解题思路 两辆车会发生碰撞的充要条件是：位于后方的车辆速度快于前方的车辆。换言之，要使任意两辆车  和  不发生碰撞，如果车  在车  的后方（即 ），那么必须满足车  的速度不大于车  的速度（即 ）。 这个要求启发我们将问题进行转化：  首先，我们将所有的车辆按照其初始位置  从小到大进行排序。 排序后，我们就得到了一个按位置排列的车辆序列，以及它们对应的速度序列。 要使这些车辆不发生碰撞，保留下来的车辆（保持它们...

题目链接 最长不下降子序列 题目描述 给定一个由  个正整数组成的数组 。请你计算该数组的最长不下降子序列（Longest Non-decreasing Subsequence，简称 LNDS）的长度。 对于一条子序列，要求保留原数组中的相对顺序，并满足子序列中的元素依次不小于前一个元素。 解题思路 本题要求解最长不下降子序列（LNDS）的长度。这是一个经典的动态规划问题，可以使用贪心算法结合二分查找进行优化，将时间复杂度降至 。 我们维护一个数组 ，其中  表示长度为  的所有不下降子序列中，结尾元素的最小值。显然，数组  是单调不降的。 我们遍历输入的数组  中的每一个元素 ：  如果  ...

题目链接 小红的地砖 题目描述 小红正在进行一次体能训练，场地上依次铺设了  块地砖，按照从  到  依次编号。她站在第  块地砖上，目标是走到第  块地砖。 已知走到第  块地砖需要消耗  的体力值。每一次移动，小红可以选择：  向前走  步，即从当前地砖  走到地砖 ； 向前走  步，即从当前地砖  走到地砖 。 请你帮助小红计算，从第  块地砖走到第  块地砖所需消耗的最小体力值。  解题思路 这是一个经典的动态规划问题。 我们定义  为到达第  块地砖时所消耗的最小体力值。我们的目标是求 。 要到达第  块地砖（当  时），只可能从以下两个位置跳过来：  从第  块地砖走  步。此时的...

题目链接 数楼梯 题目描述 给定一段有  阶的楼梯，你每一步可以选择上  阶或者  阶。求从楼梯底端走到顶端共有多少种不同的走法。由于答案可能很大，请将结果对 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 到  的耗时) + (从  到  的耗时)。空间跃迁本身不耗时。 为了快速计...