题目 石板问题 石板问题（通用跳跃版） 机器人走路 股票投资决策问题 知识闯关大冒险 最小花费爬楼梯 三角形路径挑战 石板问题 题目大意 你站在第 1 块石板上，每次可以走 1 块或 2 块石板，问你有多少种方法恰好走到第 nnn 块石板上。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 起点固定在第 1 块石板； * 目标是第 nnn 块石板； * 每步可以跳 1 或 2 格； * 问一共有多少种合法路径能走到第 nnn 块石板。 这实际上是一个变形的 爬楼梯问题，标准动态规划模型。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路（动态规划） 状态设计 设 f[i]f[i]f[i] 表示恰好走到第 iii 块石板的方案数。 状态转移方程 因为每一步可以从 i−1i-1i−1 或 i−2i-2i−2 跳到 iii，所以有： f[i]=f[i−1]+f[i−2]f[i] = f[i-1] + f[i-2]f[i]=f[i−1]+f[i−2] 初始条件 * f[1]=1f[1] = 1f[1]=1：站在第 1 块，就是 1 种方案。 * f[2]=1f[2] = 1f[2]=1：从 1 → 2，也只有一种方法。 答案 输出 f[n]f[n]f[n] 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 状态数：O(n)O(n)O(n) 个状态； * 每个状态转移耗时 O(1)O(1)O(1)； * 整体时间复杂度为 O(n)O(n)O(n)； * 空间复杂度也是 O(n)O(n)O(n)，若用滚动数组可降至 O(1)O(1)O(1)（但这不是本题重点）。 数据范围 n≤45n \le 45n≤45，故该解法非常高效。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 石板问题（通用跳跃版） 题目大意 你站在第 1 块石板上，每一步可以跨越 111 到 kkk 块石板，问你一共有多少种方法可以恰好走到第 nnn 块石板上，答案对 114514114514114514 取模。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个变种爬楼梯问题，允许步长为 111 到 kkk。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 设 f[i]f[i]f[i] 表示从第 1 块石板恰好走到第 iii 块石板的方案数。 则状态转移为： f[i]=∑j=1kf[i−j]当 i−j≥1f[i] = \sum_{j=1}^{k} f[i-j] \quad \text{当 } i-j \geq 1f[i]=∑j=1k f[i−j]当 i−j≥1 注意： * 初始时 f[1]=1f[1] = 1f[1]=1（从第1块出发，不动就是1种方式） * 对于所有 iii，我们只从之前 kkk 步内的状态转移过来。 * 所有计算均取模 114514114514114514。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 外层循环 O(n)O(n)O(n)； * 内层最多循环 kkk 次； * 整体时间复杂度：O(nk)O(nk)O(nk)； * 空间复杂度：O(n)O(n)O(n)； * 数据范围：1≤n≤105, 1≤k≤1001 \leq n \leq 10^5,\ 1 \leq k \leq 1001≤n≤105, 1≤k≤100，在时间限制内可以通过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 机器人走路 题目大意 给一个 n×mn \times mn×m 的网格，机器人从左上角 (1,1)(1,1)(1,1) 出发，每次只能向右或下走一步，求走到右下角 (n,m)(n,m)(n,m) 的不同路径总数，答案对 114514114514114514 取模。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个典型的动态规划（DP）路径计数问题。本质上是求从左上角走到右下角的组合数路径问题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 状态表示： 令 dp[i][j]dp[i][j]dp[i][j] 表示从 (1,1)(1,1)(1,1) 走到 (i,j)(i,j)(i,j) 的路径总数。 状态转移： 每个位置 (i,j)(i,j)(i,j) 的路径数等于其上方和左方的路径数之和： dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1] 因为： * 从 (i−1,j)(i-1,j)(i−1,j) 向下可以到 (i,j)(i,j)(i,j)； * 从 (i,j−1)(i,j-1)(i,j−1) 向右可以到 (i,j)(i,j)(i,j)。 边界条件： * dp[1][1]=1dp[1][1] = 1dp[1][1]=1，表示起点的路径数为 1； * 对于边界第一行和第一列，只能从一个方向走。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 状态数量：O(n⋅m)O(n \cdot m)O(n⋅m)； * 每个状态转移：O(1)O(1)O(1)； * 总时间复杂度：O(n⋅m)O(n \cdot m)O(n⋅m)； * 空间复杂度：O(n⋅m)O(n \cdot m)O(n⋅m)； * 在 n,m≤1000n, m \leq 1000n,m≤1000 的情况下，可以通过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 股票投资决策问题 题目大意 给定一个长度为 nnn 的整数数组 aaa，其中 aia_iai 表示第 iii 天股票价格的涨跌幅度（正数表示涨，负数表示跌）。你需要选择一个连续子数组，使得子数组的元素和最大。输出这个最大收益值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 可以看成一个一维数组求最大子段和的问题。 * 需要找一个连续区间 [l,r][l, r][l,r]，使得 ∑i=lrai\sum_{i=l}^{r} a_i∑i=lr ai 最大。 * 即便所有数都是负数，也要选择一个最小的负数（至少要选一天）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 状态表示： * 令 dp[i]dp[i]dp[i] 表示以第 iii 天为结尾的连续区间的最大收益。 状态转移： * dp[i]=max⁡(dp[i−1]+a[i], a[i])dp[i] = \max(dp[i-1] + a[i],\ a[i])dp[i]=max(dp[i−1]+a[i], a[i]) 意思是：要么接上前面的最大段（继续累计），要么重新开始从第 iii 天开始。 初始值： * dp[1]=a[1]dp[1] = a[1]dp[1]=a[1]，因为第一个数只能自己成段。 最终答案： * 所有 dp[i]dp[i]dp[i] 中的最大值，即 max⁡(dp[1∼n])\max(dp[1 \sim n])max(dp[1∼n]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 时间复杂度：O(n)O(n)O(n)，只需遍历一次数组； * 空间复杂度：O(n)O(n)O(n)，但可进一步优化为 O(1)O(1)O(1)（只记录上一个状态和答案）； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 知识闯关大冒险 题目大意 给出一个整数数组 aaa，其中 aia_iai 表示第 iii 个关卡可以获得的知识点数。你最多可以选取一些不相邻的关卡，使得获得的知识点总和最大。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 不能选相邻关卡，意味着如果选了第 iii 个关卡，就不能选 i−1i-1i−1。 * 本质是一个子序列选择问题，但有相邻元素限制。 * 动态规划是最自然的思路。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 定义状态： * dp[i]dp[i]dp[i] 表示前 iii 个关卡中，在不挑战相邻关卡的前提下最多可以收集的知识点数量。 状态转移： * 对于第 iii 关，有两种情况： 1. 不选第 iii 个：那最多是 dp[i−1]dp[i-1]dp[i−1] 2. 选第 iii 个：那第 i−1i-1i−1 个不能选，总和为 dp[i−2]+a[i]dp[i-2] + a[i]dp[i−2]+a[i] * 所以状态转移方程为： dp[i]=max⁡(dp[i−1], dp[i−2]+a[i])dp[i] = \max(dp[i-1],\ dp[i-2] + a[i])dp[i]=max(dp[i−1], dp[i−2]+a[i]) 初始值： * dp[1]=a[1]dp[1] = a[1]dp[1]=a[1] * dp[2]=max⁡(a[1],a[2])dp[2] = \max(a[1], a[2])dp[2]=max(a[1],a[2]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 时间复杂度：O(n)O(n)O(n)，一次遍历计算所有状态； * 空间复杂度：O(n)O(n)O(n)，如果使用数组存储全部状态；可以优化成 O(1)O(1)O(1) 空间。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最小花费爬楼梯 题目大意 给定一个长度为 nnn 的数组 aaa，其中 aia_iai 表示踩在第 iii 个台阶上的花费。你从第 000 层出发，每次可以跳一阶或两阶，问最小花费爬到第 nnn 层（楼顶，不用支付代价）是多少。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 台阶编号为 0∼n−10 \sim n-10∼n−1； * 终点是第 nnn 层，不需要付费； * 起点可以从第 0 或第 1 个台阶起跳； * 每次只能跳 1 或 2 阶； * 最后一步可以从 n−1n-1n−1 或 n−2n-2n−2 跳到楼顶。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 令 dp[i] 表示跳到第 iii 个台阶所需的最小花费，则： * 初始状态： dp[0]=a[0],dp[1]=a[1]dp[0] = a[0],\quad dp[1] = a[1]dp[0]=a[0],dp[1]=a[1] * 状态转移方程： dp[i]=min⁡(dp[i−1], dp[i−2])+a[i]dp[i] = \min(dp[i-1],\ dp[i-2]) + a[i]dp[i]=min(dp[i−1], dp[i−2])+a[i] * 注意：我们的目标是跳到“第 n 层（楼顶）”，不需要再支付费用，因此最终结果是： min⁡(dp[n−1], dp[n−2])\min(dp[n-1],\ dp[n-2])min(dp[n−1], dp[n−2]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 时间复杂度：O(n)O(n)O(n) * 空间复杂度：O(n)O(n)O(n)（可优化到 O(1)O(1)O(1)） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三角形路径挑战 题目大意 给你一个数字三角形，从顶端出发，每一步只能向下一行的相邻两个位置之一走，问从顶到底的最小路径和是多少。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 本质是一个有结构限制的路径最优化问题。 * 如果当前在第 iii 行第 jjj 个位置，则下一步只能走到第 i+1i+1i+1 行的第 jjj 或第 j+1j+1j+1 个位置。 * 求从顶部到底部的路径总和最小值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用动态规划（DP），核心思想是自顶向下或自底向上进行状态转移。 令 dp[i][j] 表示从顶端走到第 iii 行第 jjj 个位置的最小路径和。 * 状态转移方程： dp[i][j]=min⁡(dp[i−1][j],dp[i−1][j−1])+a[i][j]dp[i][j] = \min(dp[i-1][j], dp[i-1][j-1]) + a[i][j]dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+a[i][j] * 边界情况： * dp[1][1] = a[1][1] * 为防止访问越界，可以在初始化 dp[i][j] 时全部赋值为一个很大值（如 10910^9109），然后只在合法下标内转移。 * 最终答案： * 是最底层的所有 dp[n][i] 中的最小值，即： min⁡(dp[n][1],dp[n][2],...,dp[n][n])\min(dp[n][1], dp[n][2], ..., dp[n][n])min(dp[n][1],dp[n][2],...,dp[n][n]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 状态数：每层 iii 有 iii 个元素，总状态数为 O(n2)O(n^2)O(n2)； * 每个状态计算复杂度为 O(1)O(1)O(1)； * 总时间复杂度为 O(n2)O(n^2)O(n2)，可接受。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示

题目 求和 桐桐撒金币 【前缀和与差分】小码君的荣耀 投票箱 卡牌 暴躁的病人 求和 题目大意 给定 nnn 个整数 a1,a2,…,ana_1, a_2, \dots, a_na1 ,a2 ,…,an ，要求计算所有两两不同的乘积之和，即： S=∑1≤i<j≤nai⋅ajS = \sum_{1 \le i < j \le n} a_i \cdot a_jS=∑1≤i<j≤n ai ⋅aj 例如，当 a=[1,2,3]a = [1, 2, 3]a=[1,2,3] 时： S=1⋅2+1⋅3+2⋅3=11S = 1 \cdot 2 + 1 \cdot 3 + 2 \cdot 3 = 11S=1⋅2+1⋅3+2⋅3=11 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 本题目要求计算 ai⋅aja_i \cdot a_jai ⋅aj 的总和，满足 1≤i<j≤n1 \le i < j \le n1≤i<j≤n。 直接做法是使用两层循环枚举所有的 i,ji, ji,j，时间复杂度为 O(n2)O(n^2)O(n2)，当 nnn 较大时会超时。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 我们可以利用数学变形将其优化为线性算法。 观察下面的展开形式： S=a1⋅(a2+a3+⋯+an)+a2⋅(a3+⋯+an)+⋯+an−1⋅anS = a_1 \cdot (a_2 + a_3 + \dots + a_n) + a_2 \cdot (a_3 + \dots + a_n) + \dots + a_{n-1} \cdot a_nS=a1 ⋅(a2 +a3 +⋯+an )+a2 ⋅(a3 +⋯+an )+⋯+an−1 ⋅an 即： S=∑i=1n−1ai⋅(∑j=i+1naj)S = \sum_{i=1}^{n-1} a_i \cdot \left( \sum_{j=i+1}^{n} a_j \right)S=∑i=1n−1 ai ⋅(∑j=i+1n aj ) 因此，我们可以： 1. 先计算前缀和数组 prei=∑k=1iakpre_i = \sum_{k=1}^{i} a_kprei =∑k=1i ak ； 2. 对于每个 aia_iai ，它的贡献是 ai⋅(pren−prei)a_i \cdot (pre_n - pre_i)ai ⋅(pren −prei )； 3. 将所有这些贡献累加得到答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 计算前缀和：O(n)O(n)O(n)； * 枚举每个 iii 计算贡献：O(n)O(n)O(n)； * 总时间复杂度为 O(n)O(n)O(n)； * 空间复杂度为 O(n)O(n)O(n)（用于存储数组和前缀和）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 桐桐撒金币 题目大意 桐桐在一条公路上撒金币，每一公里都有一些金币。你需要处理 kkk 次询问，每次询问某一段区间 [l,r][l, r][l,r] 上金币的总和。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 本题本质是一个经典的区间和查询问题。 给定一个长度为 nnn 的数组 aaa，和 kkk 个区间 [l,r][l, r][l,r]，每次要回答： 区间和=al+al+1+⋯+ar\text{区间和} = a_l + a_{l+1} + \dots + a_r区间和=al +al+1 +⋯+ar 直接每次遍历 [l,r][l, r][l,r] 会超时，最坏情况下时间复杂度 O(nk)O(nk)O(nk)。 我们考虑使用前缀和优化查询，将每次查询降为 O(1)O(1)O(1)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用前缀和数组 preprepre： * 定义 pre[i]=a1+a2+⋯+aipre[i] = a_1 + a_2 + \dots + a_ipre[i]=a1 +a2 +⋯+ai * 则有： 区间[l,r]的和=pre[r]−pre[l−1]\text{区间} [l, r] \text{的和} = pre[r] - pre[l - 1]区间[l,r]的和=pre[r]−pre[l−1] 实现步骤： 1. 输入数组并构建前缀和； 2. 对每个区间查询，使用前缀和快速计算答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 构建前缀和数组：O(n)O(n)O(n)； * 每次查询使用 O(1)O(1)O(1)，共 kkk 次，总计 O(k)O(k)O(k)； * 总时间复杂度为 O(n+k)O(n + k)O(n+k)； * 空间复杂度 O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 投票箱 题目大意 有 NNN 个城市，总共 BBB 个投票箱。第 iii 个城市有 aia_iai 名选民。现需为每个城市分配至少一个投票箱，且每位选民必须在其城市被分配的投票箱中投票。每个投票箱可以服务一定数量的选民。 目标是通过合理分配投票箱，使得“单个投票箱服务的最大人数”尽可能小。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一道最小化最大值的优化问题。 * 每个城市必须分至少一个箱子。 * 每个城市内，可以将人口均匀分配到多个箱子中，向上取整即为该城市所需投票箱数。 * 我们要找的是一个值 xxx，使得所有城市中，任意一个投票箱服务的人数不超过 xxx，且所需的总投票箱数量不超过 BBB。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 二分答案 我们可以二分答案 xxx（即单个投票箱服务的人数），判断是否存在一个分配方案使得所有选民都能完成投票且不超过 BBB 个箱子。 2. 检查函数 CHECK(X) 对于当前猜测的最大投票箱负载 xxx，我们要判断是否可以在不超过 BBB 个投票箱的前提下覆盖所有人口： * 每个城市 iii 至少需要 ⌈aix⌉\left\lceil \frac{a_i}{x} \right\rceil⌈xai ⌉ 个箱子； * 累加所有城市所需的箱子数是否小于等于 BBB。 如果可以，说明 xxx 还可以继续减小；否则 xxx 太小了，不能满足要求。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 每组数据最多有 555 组。 * 二分最多查找 log⁡2(5×106)≈23\log_2(5 \times 10^6) \approx 23log2 (5×106)≈23 次； * 每次判断 O(N)O(N)O(N)，所以总复杂度约为 O(T⋅Nlog⁡M)O(T \cdot N \log M)O(T⋅NlogM)，可以接受。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 卡牌 题目大意 有 nnn 种卡牌，第 iii 种卡牌已有 aia_iai 张。还有 mmm 张空白卡牌可以涂写，但第 iii 种卡牌最多可以涂写 bib_ibi 张。现在你要尽可能多地组成“完整套牌”，即每套包含每种卡牌各一张。问：最多能组成多少套完整的卡牌？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 每组成一套完整的卡牌，需要每种卡牌各一张。若某种卡牌数量不够，可使用空白卡牌进行补充，但不能超过该种牌可手写上限 bib_ibi ，总手写卡牌数量不能超过 mmm。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用二分答案来判断最多能组成多少套完整的卡牌： 1. 枚举可以组成的套数 xxx； 2. 对于每个种类的卡牌： * 如果已有 ai≥xa_i \ge xai ≥x，无需补； * 如果 ai<xa_i < xai <x，需要补 x−aix - a_ix−ai 张，且不能超过 bib_ibi ； 3. 所有需要补的数量不能超过总空白卡牌数 mmm。 为了保证复杂度最优，采用倒序线性判断（f_20() 函数）或 二分查找（f() 函数）都可以。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 最坏情况每次判断 O(n)O(n)O(n)； * f_20() 复杂度为 O(n⋅A)O(n \cdot A)O(n⋅A)，其中 A=m/n+max⁡(ai)A = m/n + \max(a_i)A=m/n+max(ai )； * f() 为 O(n⋅log⁡A)O(n \cdot \log A)O(n⋅logA)，推荐在数据范围较大时使用； * 对于 n≤2×105n \le 2 \times 10^5n≤2×105，m≤5×106m \le 5 \times 10^6m≤5×106 是可接受的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 暴躁的病人 题目大意 有 NNN 个病房，坐标分别为 x1,x2,…,xNx_1, x_2, \dots, x_Nx1 ,x2 ,…,xN ，共 CCC 个病人。 需要将这 CCC 个病人安置在病房中，使得任意两个相邻病人的距离尽可能大。 求这个“最大化的最小相邻距离”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 这是一个典型的最大化最小间距问题，类似于“放置C个元素，使它们之间的最小距离最大”。 * 约束： * 每个病人占一个病房； * 病房的坐标可能无序，需要先排序； * 目标是找到一个最小距离 ddd，使得能把 CCC 个病人安排进病房，使得任意两人之间距离至少 ddd。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 先排序 将病房坐标 xix_ixi 按升序排序。 2. 二分距离 用二分法枚举最小距离 midmidmid： * 判定函数 check(mid) 判断能否安排 CCC 个病人在病房中，使得任意两人距离至少为 midmidmid。 * 方法： * 第一个病人安排在第一个病房（下标1）； * 遍历后续病房，若当前病房和上一个安排病人的病房距离 ≥mid\ge mid≥mid，则安排一个病人； * 统计安排了多少病人，若 ≥C\ge C≥C，则说明可以用 midmidmid 距离安排，返回真。 3. 二分调整 * 初始左右边界：l=0l=0l=0，r=max⁡(x)−min⁡(x)r= \max(x) - \min(x)r=max(x)−min(x)（最大坐标差）。 * 若 check(mid) 成功，更新答案，尝试更大距离 l=mid+1l=mid+1l=mid+1； * 否则缩小距离 r=mid−1r=mid-1r=mid−1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示

题目 小蚂蚁吃米 连续自然数和 差分 语文成绩 买凤梨 小蚂蚁吃米 题目大意 有一个长度为 nnn 的数组，表示小蚂蚁每天吃的白大米数量。现在有 qqq 次查询，每次查询给出区间 [L,R][L, R][L,R]，要求输出小蚂蚁这段时间内吃的大米总数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 需要多次快速求数组区间和。 * 由于 n,qn, qn,q 可以较大，使用前缀和数组预处理。 * 查询复杂度可以降到 O(1)O(1)O(1)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 预处理前缀和数组 preprepre，其中 pre[i]=a1+a2+⋯+aipre[i] = a_1 + a_2 + \cdots + a_ipre[i]=a1 +a2 +⋯+ai 1. 对于查询 [L,R][L, R][L,R]，结果为 pre[R]−pre[L−1]pre[R] - pre[L-1]pre[R]−pre[L−1] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 连续自然数和 题目描述 给定一个正整数 MMM，找出所有连续正整数区间，区间长度至少为2，且区间内所有数之和等于 MMM。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 输入格式 一个整数 MMM。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 输出格式 按起始数字从小到大，输出所有满足条件的区间，每行两个整数，表示起始数和结束数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 利用前缀和数组快速计算区间和； * 枚举左端点 lll，对每个 lll 从 l+1l+1l+1 开始枚举右端点 rrr； * 当区间和等于 MMM 输出结果； * 当区间和超过 MMM 立即跳出该轮循环（剪枝）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 差分 题目描述 给定一个长度为 nnn 的整数序列，进行 mmm 次区间加法操作，每次操作给区间 [l,r][l, r][l,r] 上的所有元素加上一个整数 ccc。最后输出操作后的序列。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 利用差分数组可以将区间加法的操作转化为两端点的加减操作，从而实现 O(1)O(1)O(1) 时间内完成区间修改，最后再根据差分数组恢复出最终序列。 具体步骤： 1. 初始化差分数组 ddd，长度为 nnn： d[1]=a1,d[i]=ai−ai−1(2≤i≤n)d[1] = a_1, \quad d[i] = a_i - a_{i-1} \quad (2 \le i \le n)d[1]=a1 ,d[i]=ai −ai−1 (2≤i≤n) 2. 对于每个操作 [l,r,c][l, r, c][l,r,c]： d[l]+=cd[l] += cd[l]+=c 如果 r+1≤nr+1 \le nr+1≤n，则： d[r+1]−=cd[r+1] -= cd[r+1]−=c 3. 对差分数组做前缀和还原序列： ai=∑k=1id[k]a_i = \sum_{k=1}^i d[k]ai =∑k=1i d[k] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码示范 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 语文成绩 题目大意 有 nnn 个学生，给出每个学生的初始语文成绩。老师将对多个区间进行加分操作，每次给第 xxx 到第 yyy 个学生的成绩都加上 zzz 分。你需要输出所有操作完成后，全班学生的最低分。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个典型的 区间加法操作 问题，使用朴素做法每次遍历 [x,y][x, y][x,y] 区间将会导致 O(pn)O(pn)O(pn) 的复杂度，显然超时。可以使用 差分数组 优化为 O(n+p)O(n + p)O(n+p) 时间。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 设数组 aaa 表示成绩数组，差分数组 ddd 定义为： * d[1]=a[1]d[1] = a[1]d[1]=a[1] * d[i]=a[i]−a[i−1](2≤i≤n)d[i] = a[i] - a[i - 1] \quad (2 \le i \le n)d[i]=a[i]−a[i−1](2≤i≤n) 对于区间加法 [x,y][x, y][x,y] 加 zzz，只需： * d[x]+=zd[x] += zd[x]+=z * d[y+1]−=zd[y + 1] -= zd[y+1]−=z 操作完后，再通过前缀和还原原数组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 构造差分数组：O(n)O(n)O(n) * 处理 ppp 次加法操作：O(p)O(p)O(p) * 还原数组并找最小值：O(n)O(n)O(n) 总时间复杂度为：O(n+p)O(n + p)O(n+p)，完全可以应对 n,p≤5×105n, p \leq 5 \times 10^5n,p≤5×105 的数据范围。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 买凤梨 题目大意 你有 nnn 本美食书，每本书推荐了一个甜度区间 [l,r][l, r][l,r]。 如果一个甜度被 不少于 kkk 本书推荐，则这个甜度是“合适”的。 现在有 qqq 次询问，每次询问一个区间 [l,r][l, r][l,r]，你需要回答这个区间中有多少个“合适”的甜度。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 本质上是区间统计问题。 * 每本书推荐了一个甜度区间 → 相当于这个区间里的每一个甜度值 xxx 被推荐了一次。 * 若一个甜度值 xxx 被推荐的次数 ≥k\ge k≥k，则称它是合适甜度。 我们需要支持： * 快速判断一个甜度是否合适； * 快速查询某一甜度区间中有多少个甜度是合适的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用 差分数组 + 前缀和优化： 1. 使用差分数组 a[i]，对每个推荐区间 [l,r][l, r][l,r]： * a[l]+=1a[l] += 1a[l]+=1 * a[r+1]−=1a[r+1] -= 1a[r+1]−=1 2. 遍历一遍求前缀和 a[i]a[i]a[i]，得到每个甜度值被推荐了多少次。 3. 另设一个数组 ok[i]，如果 a[i]≥ka[i] \ge ka[i]≥k，则令 ok[i] = 1，否则为 000。 4. 再对 ok[i] 求前缀和。 5. 对于每次询问 [l,r][l, r][l,r]，答案就是 ok[r] - ok[l-1]。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 差分与前缀和：O(MAX)O(\text{MAX})O(MAX)，其中 MAX=2×105\text{MAX} = 2 \times 10^5MAX=2×105 * 每次询问时间复杂度：O(1)O(1)O(1)，共 qqq 次，总代价 O(q)O(q)O(q) * 总时间复杂度：O(n+MAX+q)=O(2×105)O(n + \text{MAX} + q) = O(2 \times 10^5)O(n+MAX+q)=O(2×105) 级别 可以应对所有数据范围。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现

这题都做不出来吗！ 入机

T1：50! 题干信息解读： 题目要求输出固定图案，无输入处理 输出格式严格固定为5行7列 图案表示数字50的图形化显示 实现方案： 直接使用字符串数组存储图案 逐行输出预定义的图案 无需任何计算过程 方法一：数组存储 复杂度分析： 时间复杂度：O(1)，仅执行固定次数的输出操作5 空间复杂度：O(1)，使用固定大小的字符串数组存储图案5 注意事项： 图案必须严格匹配样例输出 每行末尾不能有多余空格 行末需要换行符 直接硬编码图案是最简单可靠的解决方案 cout方法： printf方法： 复杂度分析： 时间复杂度：O(1)，仅执行固定次数的输出操作 空间复杂度：O(1)，不依赖输入规模，使用固定内存 两种实现方式在性能上没有实质性差异 T2：农场修缮 题干信息解读 农场是一个n×m的网格 需要修建： 1一条固定宽度a的水平道路 2一条从q个备选宽度中选择的垂直道路 两条道路会有交叉重叠部分 目标是计算剩余的最大可耕种面积 整体做题思路 剩余面积 = 总面积 - 道路面积 + 重叠部分 数学推导可得：剩余面积 = (n - a) × (m - b) 要使剩余面积最大，需要选择最小的b值 因此只需在给定的b数组中找出最小值 题目难点和注意事项 理解道路交叉部分的面积计算 注意数据范围可能导致的整数溢出 需要高效地找出b数组中的最小值 输入规模较大时要注意算法效率 复杂度分析 时间复杂度：O(q)，因为需要遍历q个b值找最小值 空间复杂度：O(q)，用于存储b数组 在题目给定的约束下(1≤q≤10000)，这个复杂度完全可接受 T3：赛马大会 题干信息解读 题目描述了两支马队的比赛，每队各有n匹马，按照固定顺序出战1 比赛规则： 速度快的马得3分 平局双方不得分 速度慢的马扣3分 需要计算小明队伍的总得分 整体做题思路 同时遍历两个马队的数组 逐对比较马匹速度 根据比较结果累加得分： a[i] > b[i]：总分+3 a[i] == b[i]：总分不变 a[i] < b[i]：总分-3 题目难点和注意事项 数据规模较大(n≤1e5)，需要使用O(n)算法 注意整数溢出问题，总分可能达到3e5 输入输出效率对时间限制敏感（但建议还是用cin cout） 时间复杂度：O(n)，需要遍历所有马匹一次 空间复杂度：O(n)，需要存储两个马队的速度数组 T4:小明和藏宝库 题干信息解读 题目描述小明需要找到一个数字，该数字能够解锁所有n个宝箱。每个宝箱有m个不同的密码，只要数字匹配其中任意一个密码即可解锁该宝箱。目标是统计能同时解锁所有宝箱的数字个数‌ 关键信息点： 输入包含n个宝箱，每个宝箱有m个密码 密码范围1≤a_ij≤100000 需要找出同时存在于所有宝箱密码集合中的数字 输出满足条件的数字个数 整体做题思路 ‌数据收集‌：读取所有宝箱的密码集合 ‌交集计算‌：找出所有宝箱密码集合的交集 ‌结果输出‌：统计交集元素数量 核心算法是集合交集运算，需要高效处理最多5000个宝箱，每个宝箱最多5000个密码的情况‌ 题目中的难点和注意事项 ‌大数据量处理‌：n和m都可能达到5000，需要O(nm)的算法 ‌内存限制‌：128MB内存需合理使用数据结构 ‌时间限制‌：1秒时间限制要求算法复杂度不超过O(nm) ‌密码范围‌：密码值可能达到100000，适合用数组计数 ‌密码唯一性‌：每个宝箱的m个密码互不相同 T5；指针夹角 整体做题思路 计算时钟指针夹角的核心在于分别计算时针和分针相对于12点位置的角度，然后求两者差值的较小值。具体步骤为： 计算分针角度：每分钟6度（360°/60分钟） 计算时针角度：每小时30度（360°/12小时）加上每分钟0.5度（30°/60分钟） 计算绝对差值后取min(差值,360-差值)得到较小夹角 题目难点和注意事项 ‌时针的复合运动‌：时针位置受小时和分钟共同影响，需加上分钟带来的偏移量 ‌12小时制处理‌：当输入为0时应视为12点位置 ‌角度方向判断‌：需考虑顺时针和逆时针两种方向的较小夹角 ‌浮点精度‌：分钟对时针的影响是0.5度/分钟，需用浮点数计算 ‌时间复杂度‌：O(1) 仅进行固定次数的算术运算，与输入规模无关 ‌空间复杂度‌：O(1) 只使用常数级别的存储空间（几个double变量）， T6：（重磅题目）小明的ACM罚时 整体做题思路 ‌数组存储‌：使用固定大小的二维数组存储队伍信息 ‌罚时计算‌：为每道题维护错误次数和通过状态 ‌手动排序‌：实现冒泡排序处理多条件排序 题目难点和注意事项 ‌数组大小限制‌：需预先分配足够空间（n≤100，题目数≤13） ‌状态记录‌：需要同时跟踪每道题的通过状态和错误次数 ‌排序稳定性‌：确保相同条件下按队伍编号排序 ‌时间复杂度‌：O(n²) - 冒泡排序主导，n≤100时完全可接受 ‌空间复杂度‌：O(n) - 使用固定大小数组，problems数组大小100×13×2=2600个int

> 逻辑运算符 的结果是 0 或者 1 > and or not > 逻辑与：&&（and） > 逻辑或：||（or） > 逻辑非：!（not） 普通年份：2025 不能被100整除 世纪年份：1900, 2000, 2100, 2200 能被100整除 普通闰年：2020, 2024, 2028 被4整除 世纪闰年：2000, 2400 被400整除 一门课不及格 某年某月 字符判断

不一定要用set，用sort(排序)+unique(去重)也行 unique的返回值是数组末尾的地址，用返回值减数组地址就得到m

完全不会啊！ 有哪位大佬来帮帮我啊！我只是一个小白啊！ (┬﹏┬)(┬﹏┬)(┬﹏┬)

那我必须认真做了

交替报数 融合字符串

测试点1: 10 1 1 5 测试点2: 20 3 10 5 5 3 8 6 测试点3: 50 5 20 10 15 8 12 7 10 5 8 4 测试点4: 100 4 30 20 25 15 20 12 18 10 测试点5: 80 6 40 30 30 25 25 20 15 10 12 8 10 5 测试点6: 30 2 16 14 14 12 测试点7: 150 7 50 40 40 35 30 28 25 22 20 18 15 12 10 8 测试点8: 60 3 25 20 20 18 18 15 测试点9: 200 8 60 50 50 45 40 38 35 32 30 28 25 24 20 18 15 12 测试点10: 70 4 32 30 28 25 20 18 15 10

先说明一下：本人第一次写全题解，还请各位大佬指点 这次欢乐赛个人难度中等偏下，废话不多说正片开始 题目列表传送门 T1 50！ 官方难度：入门 知识点：输入输出 纯属签到题没啥可说的，直接输出就行了。 C++ Code： T2 农场修缮 官方难度：入门 知识点：循环结构 把竖直道路的宽度用sort从小到大排序求出最小值，因为剩余面积与道路的位置无关，所以可以假设水平道路在最上方，竖直道路在最左边，剩余部分为一个长方形，用(行数n-水平道路宽度a)*(列数m-竖直道路宽度)求出剩余面积。 C++ Code： T3 赛马大会 官方难度：入门 知识点：循环结构 依题意模拟即可，可以边输入对手的马匹的速度值便判断小明的输赢 C++ Code： T4 小明和藏宝库 官方难度：入门 知识点：循环嵌套 用一个数组存每个密码的出现次数，因为每个宝箱的密码互不相同，所以如果一个密码出现次数为n，则这个密码可以解锁全部宝箱。 C++ Code： T5 指针夹角 官方难度：入门 知识点：格式化输入输出 这个题目还是要考察亿点数学知识的。 设指针指向12为0°(下同)，夹角度数可以表示为 | 时针度数-分针度数 | (如果该度数大于180°，则用360°-该度数) 。注意，这道题中的时针不是在一个小时内一直指着一个数不动的那种，会根据分针移动，所以时针度数为 一大格的度数30°*(小时数+分钟数/60分钟)。分针度数不多说了，就是 一小格的度数6°*分钟数。 C++ Code： T6 小明的ACM罚时 官方难度：普及- 知识点：结构体排序 这道题比以上5道题还是难一些的，但也没有多难。 阅读题目，不难发现，一道题目的第i次提交(i>1)和第i-1次提交没有任何的关系(因为通过的时间指的是当前的时间，而不是两次提交的间隔时间)，所以遍历每一次提交记录，如果通过了罚时就增加通过的时间，如果没通过罚时就增加15分钟。然后在结构体里存该队的通过题数、罚时和队伍编号，按照题目要求排序就行了。 C++ Code： 本次全题解结束，再见~

简单吗？

统计0 计算鞍点

引号是中文，改成英文

苹果和虫子 温度转换 循环取位数 > %10：取出个位 > /10：删除最后一位

[