讨厌鬼进货 思路 这道题乍一看有三种进货方式，感觉挺复杂？别急，咱们理一下：  每种货物可以从供应商 1 买，花 a[i] 也可以从供应商 2 买，花 b[i] 还有个网购平台，花 c 元一次性买齐所有 n 种  那问题来了——如果不用网购平台，怎么买最便宜？是不是每种货物都挑两个供应商里便宜的那个就行了？对，就是 min(a[i], b[i]) 逐个取最小值，然后加起来。 那网购平台呢？它是一口价 c 元买齐全部，不能拆分。所以要么全用网购，要么完全不用网购、每种货物自己从供应商里挑。 > 等等，能不能"部分从供应商买 + 网购也买"混着来？ 可以混着来，但你想想：...

小红的地砖 思路 经典的动态规划入门题。小红站在第 1 块地砖上，想到达第  块地砖，每次可以往前走 1 步或 2 步，踩到每块砖都会消耗对应的体力值，求最小体力消耗。 是不是很眼熟？这就是「爬楼梯」问题的变体——加上了每一格的代价。 状态定义 设  表示从第 1 块砖走到第  块砖的最小体力消耗。 转移方程 第  块砖只可能从第  块或第  块走过来，所以： $$ 初始值  （起点不消耗体力） （只能从第 1 块走一步到第 2 块）  举个例子 以样例 1 为例，：             0 0 - - 0   1 3 - - 3   2 2 3 0 0+2=2   3 1 2 3 2+1...

小红的魔法药剂 思路 题目在说什么？有  种魔法药剂，每种药剂有红色和蓝色两种形态。你需要让每种药剂至少拥有一种形态。获得方式有两种：  直接购买红色药剂 ，花费  金币 合成蓝色药剂 ：消耗各一瓶红色药剂  和 （不额外花费，但原料被消耗）  问最少花多少金币？ 关键观察 注意到合成蓝色药剂  需要消耗红色药剂  和 。这意味着如果你要用红色药剂  去做合成的原料，你需要额外买一份，和你自己留着用的那份是独立的。 换句话说，每次合成都是独立事件——需要专门为它购买原料，不存在"一份红色药剂既当原料又当收藏品"的情况。 那么对于每种药剂 ，我们就有两个独立的选择：  选红色...

小红的优惠券 思路 这题在说什么？小红要结账了，手里有一堆优惠券，每张券都是"满 X 元减 Y 元"的类型，她最多只能用一张，问最少要付多少钱。 那我们的目标就很明确了：在所有能用的优惠券里，挑减免金额最大的那张用。 什么叫"能用"？就是购物金额 >= 这张券的门槛 X。不满足门槛的券直接跳过。 所以做法就是：遍历所有优惠券，如果当前金额够得着这张券的门槛，就记录一下它的减免金额，取最大值。最后用购物金额减去这个最大减免值就是答案。 如果一张券都用不了呢？那最大减免值就是 0，答案就是原价，完全不用特判。 这就是典型的贪心思路——在所有合法选项中选...

小红的整数配对 思路 题意：给 n 个整数和一个阈值 m，每次可以选两个还没被选过的数配对，条件是两数之差的绝对值不超过 m，配对得分为两数之积。问最大总得分是多少。 贪心策略很直觉——大数配大数，收益最高。具体怎么做？  排序。排完序后，能配对的数一定是"挨得近"的，因为差值不超过 m。 从右往左贪心配对。从最大的数开始看，如果它和前一个数的差 <= m，就把它俩配上（乘积最大化），然后跳过这两个继续往左看；如果差值 > m，说明当前这个数找不到合法的配对伙伴（左边的只会更小，差值只会更大），只能放弃它，往左移一位。  为什么从右往左贪心是对的？排序后，最大的...

被打乱的异或和 思路 题目说的是：有一个长度为  的原始数组，把所有元素异或起来得到 ，然后把  追加到数组末尾变成长度  的数组，再随机打乱顺序给你。问原始数组的异或值是多少。 乍一看好像得想办法把  从打乱的数组里"找出来"，但仔细想想会发现一个关键性质： 打乱后数组所有  个元素的异或值一定是 0。 为什么？设原始数组为 ，那么 。打乱后的数组包含这  个元素加上 ，全部异或起来就是： $$ 这意味着什么呢？对于数组中的任意一个元素 ，把它当作被追加的那个 ，剩下的  个元素的异或值恰好就是  本身（因为总异或是 0，去掉  后异或值就是 ）。 所以每种拆分方式都是合...

最长异或公共子段 思路 题目给了两个不同的非负整数 ，分别生成两个无限序列  和 （）。要求找到最长的公共连续子段长度 。 "公共连续子段"意味着存在  使得对所有 ，有 ，即： $$ 两边同时异或，等价于： $$ 其中  是个固定值。 关键转化 问题变成：找最大的 ，使得存在 ，对连续  个  值都有 。 取 ，设 ，则条件变为  对连续  个  成立。 当我们选  时，条件变成 。什么时候  呢？恰好是  和  没有公共的 1-bit，即  的时候。 所以问题进一步简化为：最长的连续整数段 ，满足每个数与  按位与为 0。 lowbit 就是答案 设  的最低位的 1 ...

植树节 思路 题目在说什么？有  个志愿者，每人负责给编号  的树苗各浇一次水，问被浇水次数最多的树苗被浇了多少次。 这是经典的差分数组问题。对区间  全部加 1，等价于在差分数组上 ++ 和 --。所有操作做完后，对差分数组求前缀和就能还原每个位置的实际值，取最大值即可。 复杂度  时间：，其中  是坐标上界（） 空间：  代码    C++   Java   Python3   JavaScript   #include <bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d", &...

染色 思路 题目说的是：有  个油漆桶，初始都是白色。进行  次操作，每次往区间  的油漆桶里加一种颜料（1=黄色，2=蓝色，3=红色）。颜料混合规则：黄+蓝=绿，黄+红=橙，蓝+红=紫，三色全加=棕。问最终有多少桶是绿色的。 绿色的条件是什么？有黄、有蓝、没有红。 这是一个典型的差分数组问题。区间加操作用差分数组来做是最自然的。 关键在于：三种颜料是独立的，每种颜料只需要知道"有没有被加过"。所以我们对三种颜料分别维护一个差分数组。 具体做法：  开三个差分数组 ，分别对应黄、蓝、红三种颜料。 对于每次操作 ，在对应的差分数组上做 ++，--。 最后扫一遍，对三个差分数组...

斐波那契字符串 思路 题目定义了斐波那契字符串：，，（拼接）。要求统计  中的逆序对数量，即满足  且 ， 的  对数，结果对  取模。 显然不能把字符串构造出来暴力数，因为长度是斐波那契级别增长的。我们需要找递推关系。 ，所以  的逆序对来自三部分：  左半部分  内部的逆序对  右半部分  内部的逆序对  跨越左右的逆序对：左边的 '1' 和右边的 '0' 配对   所以核心递推式： $$ 其中  和  分别是  中 '1' 和 '0' 的个数，它们也满足斐波那契递推：     用样例验证：  ：，。正确！ ：，。正确！  由于有多组查询（ 可达 5000， 可达 ），我们预处理所有  的...

卡牌游戏 思路 题目说的是：有  张卡牌排成一排，每次操作可以从最左边选至少 2 张连续卡牌，把它们合并成一张（值为总和），得分加上这个总和。可以随时停止操作，问最大得分是多少。 关键观察：设前缀和 。 第一次合并前  张牌，得分是 。第二次合并当前最左边的若干张（合并后的牌 + 至少一张新牌），得分是 （因为合并后的牌值就是之前的前缀和，加上新牌就是更长的前缀和）。 以此类推，每次操作的得分恰好是某个前缀和 ，而且这些下标构成严格递增序列，起点 。 那问题就变成了：从  中选一个子集，使得对应前缀和之和最大。 这太简单了！每个位置独立决策——前缀和为正就选，为负就不选。 $$ 一次遍历搞定，...

BGN58: 空间跃迁 思路 有  个城市排成一条线，相邻城市之间有行走耗时。你从城市 1 出发要到城市 ，中途可以使用一次空间跃迁，半径为 ，也就是从城市  瞬间跳到城市  或 （不花时间）。 先想一下：如果不用跃迁，总耗时就是所有相邻城市之间耗时的总和。用了跃迁之后呢？从城市  跳到城市 ，相当于跳过了从  到  这一段连续  条边的费用。往回跳到  没有意义，因为我们最终还是要往前走。 所以问题就变成了：在  条边中，找一段连续  条边，使得它们的费用之和最大，然后从总费用中减去这个最大值。 这不就是经典的滑动窗口嘛！维护一个大小为  的窗口，滑过去找最大的窗口和就行了。 特殊情况： 时...

BGN53: 舞萌时间到！ 思路 舞萌 DX 里每次敲击音符会得到一个判定，对应不同的 dx 分：    判定 字符 dx 分     Critical Perfect P 3   Perfect p 2   Great G 1   Good g 0   Miss m 0    给一个判定序列字符串，q 次询问，每次问区间  内的 dx 分总和。 这就是一道经典的前缀和模板题。把每个字符映射成对应的分值，预处理前缀和数组  表示前  个字符的分值之和，每次查询直接  回答：。 代码    C++   Java   Python3   JavaScript   #include <bits...

数楼梯 思路 经典的爬楼梯问题：一共 n 阶楼梯，每次可以走 1 阶或 2 阶，问有多少种走法。 稍微手算一下就能发现规律：  1 阶：1 种 2 阶：2 种（1+1 或 2） 3 阶：3 种 4 阶：5 种  设  表示走到第  阶的方案数。到第  阶只有两种方式——从第  阶走 1 步上来，或者从第  阶走 2 步上来，所以： $$ 初始值 （站在地面，算一种方案），。这就是斐波那契数列。 因为只需要前两个状态，所以用两个变量滚动一下就行了，空间 。注意过程中要对 998244353 取模。 代码    C++   Java   Python3   JavaScript   #includ...