1. 什么样的题才配得上“反复品味”四个字
我在AcWing上刷题也有一段时间了，从基础语法题一路做到提高课，最大的感受是：有些题，你AC了就觉得自己会了，可隔两周回头再看，发现当时的解法漏洞百出；还有一些题，第一次看题解惊为天人，但真让你自己从头推导一遍，还是卡在同一个地方。
标题里说“需要反复品味思路”，我理解的这类题目是有明确特征的。先说结论：判断一道题值不值得反复品，不是看难度标签，而是看它能不能帮你把“错误直觉”纠正过来。
一道值得品味的题，通常具备下面几个特点。
第一，它有多条解题路径，但只有一条是本质。比如用朴素枚举能过样例，数据稍大就超时；套一个常见模板能过，但你不明白为什么对；只有当你从问题性质出发重新分析，才会发现原来这是个经典模型换了一层皮。这类题的价值不在“会做”，而在“看穿”。
第二，它的解法和你的第一直觉是对着干的。最典型的就是贪心类题目，很多情况下我的第一反应是排序，但排序的键是什么、为什么这样排序能保证全局最优，这需要反复验证。还有一类状态压缩DP，第一反应是深搜，但状态数量爆炸；第一反应是线性DP，又发现没法转移，逼着你去想“怎么样表达状态才能覆盖所有情况”。
第三，它在标准解法之外藏着不止一个优化点。例如多重背包问题，你会写三层循环的朴素版，也知道二进制拆分优化，但再往下还有单调队列优化。每往深一层，你对“为什么物品个数可以按二进制分组”的理解就会更透。
第四，它能把不同章节的知识串起来。比如一道看似是搜索的题，其实底子是二分图判定；一道看似是图论的题，真正做法是DP。这种跨知识点迁移的能力，只有靠反复品才能形成肌肉记忆。
我自己有个习惯，会把刷过的题分成三类：一类是“过手题”，做完不再看；一类是“收藏题”，总结成笔记；还有一类就是“反复品味题”，专门放一个清单，每隔一段时间就回来重做一遍。标题里提到的这类题，我建议你都归入第三类。因为这些题不是你刷完一遍就会彻底掌握的，它需要你经历三次左右的重做、复盘、再思考，才能真正把思路内化。
2. 动态规划：多数“想破头”的题都在这里
先聊一个我个人的统计。在我标记为“需要反复品味”的题目里，动态规划类占了将近四成。这不是因为DP题有多难，而是因为DP的难点非常集中：状态是怎么想到的？一旦状态定义对了，转移方程往往就是顺水推舟。但状态定义恰恰是最没法靠模板解决的问题。
2.1 状态设计比转移方程更需要反复琢磨
以最长上升子序列为例，我第一次接触时觉得这题很简单：dp[i]表示以第i个数结尾的最长上升子序列长度，转移就是遍历前面所有j，如果a[j]小于a[i]就更新dp[i]。这个解法时间复杂度是O(n^2)，能处理几千的数据量。但在AcWing上有一道数据范围到10万的版本，O(n^2)直接超时。
这时候就有两种提升路径。一种是学习贪心加二分的优化：维护一个有序数组d，d[len]表示长度为len的上升子序列的最小末尾元素，遍历每个数时通过二分找到它在d中的位置。另一种思路是问自己：dp数组里的信息是否有冗余？我们真的需要知道以每个位置结尾的最长长度吗？还是只需要知道“当前长度对应的最小末尾”？
这个问题的答案就是优化的关键。我反复做了三遍这道题，每做一遍对“单调性在哪里”的理解就更深一层。第一次我只是背下了d数组的维护过程；第二次我才意识到d数组天然是递增的，否则没法二分；第三次我才真正想明白：因为我们要让末尾元素尽量小，这样后面才更容易接上更长的序列。这种“最后一遍比第一遍多看到一层东西”的感觉，就是反复品味的价值。
另外一个经典例子是数字三角形。你会写从顶部到底部取最大路径的DP，很快。但如果你反过来，从底部往上走，代码会简单很多，却并不直观。这题让我想明白了一个道理：DP的方向不一定非要顺着输入顺序，只要能保证状态依赖的方向是“已计算”的，就是合法的。有人喜欢从上往下，有人喜欢从下往上，但真正的高手会告诉你，这只是实现层面的事，关键是状态表示里有没有把“路径方向”这个信息丢掉。
2.2 背包问题变体里的“二进制拆分”值得细嚼
背包问题几乎是AcWing上动态规划的基础必修课，从01背包到完全背包，再到多重背包，一层比一层麻烦。我刷题时的感受是：01背包的一维滚动数组优化，第一次看代码能看懂，但不知道为什么内层循环要倒序。直到我自己画了一张二维表格，把每个状态的依赖关系标出来，才看明白：正序更新会让当前物品被多次使用，这恰好就是完全背包的语义。
多重背包的二进制拆分是另一个反复品味的点。基本思路是把第i种物品的数量c[i]拆成若干个2的幂次，比如7拆成1、2、4，这样任意0到7之间的数量都能用这些组的组合表示出来。我第一次看这步操作时觉得很神奇，但后来才意识到这是一条通用思路：把一种O(c[i])的枚举，转换成O(log c[i])的枚举，用二进制表示整数是计算领域的底层原理。以后再遇到“每种物品至多选若干件”的问题，我会条件反射地想到这个操作。
还有一类DP，我第一次做的时候完全是懵的，那就是状态压缩DP。最短Hamilton路径这类题，如果用朴素DFS，状态是排列级别的；但如果把“已经走过的点集合”压缩成一个二进制整数，用dp[mask][j]表示“当前走过的点集是mask，最后停在j”的最短路径，复杂度就是O(2^n * n^2)。这种思路的第一个门槛是接受“用一个二进制串表示集合”，第二个门槛是循环的顺序：要先枚举集合，再枚举集合中的点和可能的前驱点，而枚举细节错了就会导致结果偏差。
我对状态压缩DP的态度是：它值得反复品，因为它是面试和竞赛里常见的难题类型，而且它的“暴力”是聪明地暴力——把指数级枚举降到了可以接受的规模。如果你觉得集合是什么很抽象，可以想象一个整数mask，它每一位表示一个点是否已经走过，比如mask=5（二进制101）表示0号和2号点已经走过了。然后dp就是在这些mask之间做转移。每次你想扩展一步，就找一个没走过的点加进mask，更新对应的距离。
2.3 记忆化搜索是品DP的另一个角度
有些DP题目，直接写递推非常别扭，但换个角度用记忆化搜索，反而思路清晰。比如滑雪这题，要求最长下降路径，本质是DAG上的最长路。当我用深搜加备忘录实现时，代码结构是“当前这个点出发能走的最长路径 = 1 + max(相邻四个方向能走的最长路径)”，这种递归表达非常自然。这类题之所以值得反复品味，是因为它打破了“DP必须老老实实按照某个顺序填表”的思维定式。你需要理解的是：只要状态之间的依赖关系不构成环，你就可以用递归来模拟填表过程，备忘录就是DP表。
还有一个细节我开始没注意：递归的边界条件。如果某个点四周都比它高，它就不能继续走，返回值就是1。这个边界如果不写对，整个递归会陷入死循环或者答案错误。所以后来我的习惯是，写记忆化搜索之前先把递归出口写清楚，这比先写转移方程更优先。
3. 图论：第一直觉往往是最贵的坑
图论题的“反复品味”点，和DP还不太一样。DP难在状态设计，图论题难在“把问题抽象成图”以及“选对算法”。我踩过的一个大坑就是：遇到图论题第一反应套最短路径模板，却不问自己一句——题目里的“距离”到底是什么？
3.1 最短路问题里没被说透的几种变体
AcWing上有一类排队、等车的题，表面上是个走迷宫，但状态不只是二维坐标，还涉及时间或剩余步数。这时你就需要把二维网格扩展成三维状态图，每个状态是一个(行,列,剩余时间)三元组。我第一次做这类题时，习惯性地写了BFS，结果发现普通BFS不允许同一个格子走两次，但题目里链式状态允许绕路。后来我才明白：只要每个扩展出的状态节点不同，BFS的“第一次到达即最短”依然成立，因为边权为1的图上，BFS天然求的是最短路。
Dijkstra也一样。很多人背下了堆优化的代码，但遇到“边权非负”条件不满足的题就开始翻车。比如有一类题允许边权为负但不能存在负环，此时正确的算法是SPFA或Bellman-Ford。我见过很多人在Dijkstra和SPFA之间犹豫不决。其实判断标准很朴素：有负权边，用不了Dijkstra；有负环的判断需求，优先考虑SPFA；对复杂度要求高，尽量把图建得没有负权边，再用Dijkstra。
3.2 最小生成树：为什么选择边的逻辑决定了复杂度
最小生成树的Prim和Kruskal两种算法，我刚开始总觉得只是实现上的差别。直到做了几道“最小生成树的变体”题之后才意识到，两者的适用场景完全不同。Kruskal是加边法，按边权排序后从小到大选边，用并查集维护连通性，适合边少点多的稀疏图；Prim是加点法，每次加入离当前树最近的点，适合边多点少的稠密图。
有一道题是求最小生成树，但是要求“第k小的边尽量小”，这个“尽量小”其实是二分答案加并查集判定。我在这里卡了很久，因为直观上总觉得生成树只能跑一遍。实际上这种“最值套最值”的问题，很多都能用二分答案解决：猜一个答案X，把所有边权大于X的边剔除，看剩下的边能不能构成一棵生成树。如果能，说明X可以再小一点；如果不能，说明答案得再大一点。这个思路一旦点破，就很简单，但每次遇到新题，我还是会习惯性地先去想怎么造一棵树，而忘了二分答案这个通用手段。
3.3 二分图的染色判定比看起来更需要反复验证
在图论里，有一道很基础的题：判定一个图是否是二分图。做法是染色，从每个未染色的节点出发，把邻居染成相反颜色，如果冲突就不是二分图。这题难度不高，但它经常藏在别的题目里当判定子模块。比如有一些棋盘覆盖题，看起来是搜索，其实只要把棋盘按格子颜色染色，就能转换成二分图匹配或最大流问题。
我把这类题放进“反复品味”清单，是因为它的思维跨度大。你需要具备一种能力：看到一个实际问题，能把它映射成图论模型。棋盘上能互相攻击的棋子关系可以连边，墙和障碍可以拆点分列，人被分配到任务可以建二分图。这种抽象能力不是看一遍题解就能有的，得多做、多想、多复盘。
4. 贪心与二分：答案好猜，证明难写
如果说DP是状态设计难题，那贪心和二分就是“证明”难题。这两类题特别容易让人产生“我懂了”的错觉，因为答案很好猜。但一让你说明“为什么这个策略是对的”，很多人就卡住了。而在AcWing上，真正需要反复品味的题，恰恰是那些需要严格证明的题。
4.1 贪心策略的正确性到底怎么验证
合并果子是我最早接触的贪心题之一。思路很简单：每次选两堆数量最少的果子合并。正确性的直观解释是一棵哈夫曼树，越早合并的堆在后续计算中参与合并的次数越多，所以要让大堆尽量晚参与。但这里有个容易忽略的地方：如果你贪的是“合并代价和最小”，那么堆越小越好；但如果你贪的是别的目标，策略可能就反过来了。比如有些题要求尽量让大的先处理，你就得反向排序。
我总结过一个通用的验证方法：尝试构造“反例”。在纸上画情况，用一个看似正确的贪心策略去跑，看能不能找到违反结果的例子。如果你能在五分钟内找到反例，这个策略就是错的；如果怎么也构不出反例，就再用“交换论证法”尝试证明。所谓交换论证，就是假设有一个最优解和你的贪心解不一致，你尝试把最优解的一步“交换”成贪心策略的选法，看成本会不会变差。如果不会变差，就说明存在一个包含贪心选法的最优解，从而贪心成立。
这个证明方法我是在区间选点、区间覆盖这类题里反复练出来的。一开始我不会写证明，后来强迫自己每题都至少写两行“为什么贪心是对的”，慢慢就有了手感。也许有人觉得竞赛刷题只要会AC就行，但我个人的体会是，会证明的人，遇到变体题更容易活学活用。
4.2 二分答案的三板斧：单调性、判定、边界
二分答案也是需要反复品味的套路。很多题让你“最小化最大值”或“最大化最小值”，这几乎就是二分答案的信号。我第一次接触这个套路时，总觉得自己在做一个没有根据的猜测，直到我明白了三个关键点。
第一是单调性。二分答案要求判定结果随答案单调变化。比如说“最大装载量不超过X是否可行”，当X增大时，可行性只会变强不会变差，这就构成了单调性。第二是判定函数，也叫check函数，它是二分的核心。第三是边界，也就是左右端点的初始值和循环退出条件。我踩过最多次的坑就是边界：如果左边界初始化为0，右边界初始化为一个不够大的数，那么答案可能在右边界之外，直接造成漏解。
有个很实用的技巧是：二分时把问题转换成判定问题后，先纸上模拟一次，看看check函数里用大于等于还是小于等于，以及答案是靠左边界收敛还是右边界收敛。再有一个细节是整数的二分，建议用“左闭右开”的写法，避免死循环：
int l = 0, r = 1e9; // 区间左闭右开 [l, r) while (l < r) { int mid = (l + r) / 2; // 或者 (l + r) >> 1 if (check(mid)) r = mid; // 答案在 [l, mid] 范围 else l = mid + 1; }如果你是向右查找（找最大值），倒过来：满足条件就l=mid+1，否则r=mid。我个人建议把这两种写法分别固定成自己的习惯，不要每次临场想，特别容易混。
5. 数据结构题：套路的背后是取舍逻辑
AcWing上的数据结构题，从线段树、树状数组、平衡树到可持久化数据结构，每一类都很值得反复品。因为很多题目表面上考数据结构，其实考的是“为什么要选这个数据结构”。
5.1 树状数组的“单点修改、区间查询”不是万能药
树状数组是很轻量的数据结构，代码短，常数小，可以维护前缀和。但它只能维护满足“可减性”的信息，比如和、异或，不能直接用区间最大值。这时候很多人第一反应是线段树。可如果问题只是求区间最值且没有修改操作，那直接ST表更合适；如果有单点修改和区间最值查询，线段树才真正派上用场。
有一类题是区间加和区间求和，一开始我很自然想用线段树加懒标记。但AcWing上有一道区间修改、单点查询的题，其实用差分加树状数组就能解。树状数组维护差分数组，区间加就是两次单点更新，单点查询就是前缀和。这题让我反复品味的点是：区间操作和单点操作是可以互相转化的。你在决定数据结构之前，先要弄清楚题目要求的是“哪一种操作”。
我最推荐的练习方式是：同一道题，先写树状数组版本，再写线段树版本，比较两者在代码量、常数、可扩展性上的差别。比如区间最大值的题，树状数组只能做到单点修改加区间最值查询，但对区间整体的某个属性（比如区间最大值）做区间修改时，树状数组就行不通了，必须用线段树。没有这种亲手比较，你对“为什么入门的线段树代码那么长但还是得学”的理解就不会深刻。
5.2 并查集的扩展域与带权并查集很容易被忽略
并查集是我觉得性价比最高的数据结构，代码短、思想深刻。普通的并查集维护是否连通，但带上扩展域后，就能表示“朋友的朋友是朋友”这类关系之外的等价类。比如一些种类的判定题，把每个元素拆成多个域，分别为“同类域”“捕食域”“天敌域”，合并关系时只需看对应域是否冲突。
我第一次做这类题时，直接懵了：为什么要把一个动物拆成三个节点？后来想明白了，并查集的节点本质上是一个逻辑概念，不是物理对象。一个动物可以有多个身份（例如作为捕食者时的身份和作为被捕食者时的身份），每个身份用一个节点表示，关系就是这些身份之间的合并。带权并查集也是类似：除了father数组，还维护一个到根的权值，路径压缩时要同步更新权值，这要求你在合并时计算权值的偏移量。这个细节特别容易写错，值得反复品。
5.3 线段树的懒标记和动态开点是两道坎
线段树的懒标记是基础里的基础，但也是很多人半懂不懂的地方。我见过的错误中，最高频的错误是：pushdown的时候只下传了标记，没有更新子节点的值；或者查询时忘了pushdown，导致区间信息没有及时合并。
动态开点线段树是另一道坎。普通线段树需要4倍空间开数组，但动态开点可以只创建访问过的节点，适合值域很大但操作数不多的场景。我第一次接触时，不太理解为什么创建一个节点时直接把左右孩子置为0就可以了。后来才明白，0号节点是所有空节点的代表，它的值就是单位元（比如求和时为0、最值时是无穷小）。这个思想在可持久化线段树里会更进一步：每次修改只新开一条链，其他节点沿用上一版本的节点，从而实现历史版本查询。
每次我回看这些数据结构，新的理解总是在“为什么这个写法是对的”这个层面浮现。所以我建议你在看题解时，不要只看代码，而是把代码里关键的几行注释写出来，比如“这里pushdown是因为mark要在这里被使用”“这里rt的孩子可能是0号节点，需要先new出来”。这个习惯能帮你少走很多弯路。
6. 实操复盘：如何高效地把一道题“反复品”出价值
在前面的章节里，我讲了不少具体题目类型和思路。但还有一个更重要的问题：到底怎么安排反复品味的节奏，才能真正吸收？我自己试过几种方式，踩过不少坑，分享一套目前比较有效的做法。
6.1 三阶段刷题法：AC、复盘、再重做
第一个阶段是独立做题。我给自己定一个规则：先自己想30分钟，能写出多少写多少，实在没思路才看题解。这么做的好处是，即使你没解出来，你在看题解时也能知道自己卡在了哪个环节，而不是“原来有两种做法”这种泛泛的顿悟。
第二个阶段是题解复盘。看完题解后，合上题解，自己从头写一遍。注意不是默写，而是理解思路后重写。如果你能写对且能说出来这道题的核心解法，就算第一轮过。如果你写不出来，说明题解还是没看懂，那这道题就加入“待二次消化”清单。
第三个阶段是隔段时间再重做。我一般会隔一到两周，把之前标记的题再拿出来，不看题解，只看自己之前的代码和注释，然后独立重写。如果能独立AC，这道题才真正属于你。如果重写时又卡住了，那说明你第一轮吸收得不够，这种题就该再品一次。我的经验是，绝大多数“反复品味”的题，到第三遍基本能融会贯通。
6.2 写题解笔记的三个关键点
很多人写笔记就是把题解抄一遍，这其实没什么用。我自己的笔记模板包含三块内容：一是“我卡在哪了”，二是“核心思路用一句话怎么说”，三是“这题与哪道旧题相通”。
“我卡在哪了”是最有价值的一块，因为那是你思维盲区的真实记录。下次再遇到类似题，你翻笔记时看到这句话，会立刻回忆起当时的障碍。“核心思路一句话”更重要，它逼你把题解压缩成可复用的抽象模型。比如“这题本质是DAG上的最长路，用记忆化搜索”“遇到最小化最大值，先想二分答案”“区间合并操作，考虑差分加树状数组”。最后一条“与哪道题相通”能帮你把散点串成知识网络。
6.3 调试中的头痛时刻：数组越界、初始化顺序、递归爆栈
AcWing上调试经常遇到的问题，我也整理了一张速查表，每次卡住就按表排查。
第一个坑是数组越界和初始化。我在做DP题时最常犯的错是二维数组维度写反，或者是忘把dp数组初始化为一个足够小（或足够大）的哨兵值。有个细节值得强调：如果求最大值，初始化时通常用负无穷；如果求最小值，初始化用正无穷。如果不统一初始值，转移时会漏状态。
第二个坑是循环顺序。动态规划里，外循环是阶段，内循环是决策，这个顺序如果颠倒，结果大概率错。以区间DP为例，第一层循环枚举区间长度，第二层枚举起点，第三层枚举切割点，这个顺序不能变。你要是先枚举起点，再枚举长度，某些状态还没算出来就被使用了，结果就会错。
第三个坑是递归深度。DFS或记忆化搜索如果递归深度超过系统栈限制，会直接栈溢出。这时可以用两种办法：一是把递归改成显式栈模拟；二是增加栈大小（竞赛环境里可以在命令行入口处设置）。对刷题练习而言，我一般建议先判断递归深度是否在可接受范围内，比如深度是10万级别就要小心了。
6.4 这个清单怎么持续迭代
我建议你每隔一两个月，回头过一遍自己标记的“反复品味”题，看看哪些已经消化得差不多了，就移出清单。如果哪道题仍然一写就卡，说明它背后对应的知识点还是你的薄弱环节，那就围绕着它展开一轮针对性补强。
举一个我自己的例子，有一段时间我对“二分答案”的check函数总是写不对，于是在AcWing里集中刷了七八道二分相关题，把每种check函数的写法都做笔记。之后再遇到类似题，我能在几分钟内把check函数想清楚，而不是每次强行记忆。
反复品味的意义，不在于把题海战术变成题海背诵，而在于通过一次次重做，把“看别人思路”变成“自己的思路”。这个转变过程很慢，但每完成一次，你的算法能力就真正前进了一步。
最后再分享一个我很受用的习惯：当你觉得一道题特别绕、特别反直觉的时候，试着给身边的朋友讲一遍这道题。讲不清楚的地方，往往就是你没理解透彻的地方。我在几次讲题之后才意识到，能把别人讲懂，比AC这道题本身更有价值。如果你在AcWing上也有那种“看了题解觉得很简单，但隔几天又不会做”的题，千万别急着划走，把它记下来，按上面的方法反复品几次，你会发现它慢慢从“难题”变成了“基础题”。
