最近带一个备考GESP八级的学生，刷到洛谷P14924这道“宝石项链”时，他第一反应是“这不就是个环形字符串问题吗”，然后一头扎进最小表示法和区间DP里出不来。我瞄了一眼题面里的数据范围和操作方式，直接跟他说：别绕了，这就是一道典型的“倍增+动态规划”组合题。今天把这道题从读题建模到代码实现的完整思路写下来，顺便聊聊GESP八级为什么会盯上这类考法。
这道题的核心场景是：一条环形项链，每颗宝石有价值，每次操作拿走连续的一段，段长有上下界限制，问若干次操作后能拿到多少价值。表面看是“切环”“分段”的问题，骨子里考的却是两个东西：一是把“连续拿一段”抽象成“从某位置跳到下一位置”的单步动作，二是用倍增把“执行m次操作”压缩成对数级别的跳转。这两个点一打通，整道题的复杂度就从O(n×m)降到了O(n log m)，这也是GESP八级“倍增”考点的标准用法。
如果你是正在准备八级认证的选手，或者刚学完线性DP和倍增、想在洛谷上找几道综合题练手，这篇文章可以直接照着做。下面我把建模过程、状态设计、手推样例、完整代码和考场避坑一条龙讲清楚。
1. 见“项链”先破三关：读题就能拆掉的三个思维陷阱
1.1 第一关：环形结构带来的心理压力
很多选手看到“项链”“环”第一反应就是要复制数组、取模、特殊处理首尾相接。实际上在这类“从环上连续取段”的题目里，环形只是为了让“方案可能在任意位置剪开”这件事变得合法。最朴素也最稳的做法，是把项链从任意一颗宝石处“剪开”，铺成一条长度为n的链，再用一个2n的数组把这条链复制一遍。为什么要复制成2n？因为倍增跳转可能跨过链尾回到链头方向（例如从第n颗附近取段，终点落到第1颗附近），复制一份后，所有跨越剪口的区间都能用普通的下标运算表达，不用每次判断边界、不用写一堆取模特判。
这一步的关键心态是：环形不是难点，是障眼法。你真正面对的是一个线性数组上的连续区间选择问题。
1.2 第二关：把“拿一段”翻译成“指针跳一格”
“每次拿走连续的一段”这句话如果原样写进状态里，状态维度至少得有“左端点、右端点、当前操作次数”三个，直接爆炸。换个角度想：如果我现在站在位置i，段长必须在[L, R]之间，那我这次能选的终点t就在[i+L-1, i+R-1]这个区间里。价值是前缀和pre[t] - pre[i-1]，我取其中最大的一项，把最优终点记下来，那么这次操作结束后，下一个起点自然就是bestEnd + 1。
于是，一次操作变成了一次确定性跳转：从i跳到jump[i]，同时获得收益value[i]。整个问题从“区间分割问题”变成了“反复执行跳转函数的问题”。这才是倍增能介入的入口——如果你面对的是一堆区间枚举，倍增帮不上忙；但如果你面对的是一个可以反复复合的跳转函数，倍增就是为它量身定做的工具。
1.3 第三关：m次操作不是循环，是二进制拆位
如果m很小，比如m ≤ 100，直接模拟m次跳转完全可行。但GESP八级的题不会这么好心，m往往大到10^5甚至10^9量级。这时候如果还想着“一次一次跳”，评测机分分钟教你做人。
倍增的想法很直接：既然单次跳转jump[i]已经算好了，那“跳两次”就是jump[jump[i]]，“跳四次”就是在此基础上再复合一次。预处理出jump[i][k]表示“从i出发，连续执行2^k次操作后到达的位置”，查询时把m拆成二进制——比如m = 3就拆成2 + 1，先走一个“两步”，再走一个“一步”——总跳转次数从m次压缩到O(log m)次。
此处有一个初学者必踩的思维误区：觉得倍增就是“大步跳”，跟DP没关系。实际上这个模型的预处理本身就需要DP——用递推关系f[i][k] = f[f[i][k-1]][k-1]来合并子状态，这是典型的“DP合并”而非单纯的预处理。倍增和DP在这里不是两个并列的考点，而是同一个解法的两个侧面。
2. 倍增表里同时装位置和价值：状态设计是这道题的精髓
2.1 一张表负责“人在哪里”
第一张表叫jump[i][k]，含义是：从位置i出发，连续取2^k段之后，指针停在哪。这张表解决的是“状态转移的方向”。它的第0列jump[i][0]就是第1章算出来的bestEnd[i] + 1，也就是“从i拿一段之后的下一个起点”。
第k列的递推非常优雅：
- 先把2^k段拆成两个2^(k-1)段；
- 前半段从i出发，结束后停在mid = jump[i][k-1]；
- 后半段从mid出发，结束后停在jump[mid][k-1]。
写成式子就是jump[i][k] = jump[jump[i][k-1]][k-1]。这也是为什么外层循环要按k从小到大枚举——算第k列时，第k-1列必须已经全部就绪。
2.2 另一张表负责“赚了多少”
位置知道了还不够，题目要的是价值。第二张表val[i][k]表示：从i出发，连续取2^k段累计获得的最大价值。第0列val[i][0]就是第1章算出来的bestVal[i]，即站在i点选一段能拿到的最大收益。
合并方式跟jump表完全同构：
- 前半段2^(k-1)段收益为val[i][k-1]；
- 后半段从mid = jump[i][k-1]出发，收益为val[mid][k-1]；
- 总收益 = 前半段收益 + 后半段收益。
写成式子就是val[i][k] = val[i][k-1] + val[jump[i][k-1]][k-1]。
这里我特别想强调一个细节：为什么“收益”可以直接相加，而不是取最大？因为倍增合并的本质是“无缝衔接的两个子过程”——前半段结束时指针恰好停在mid，后半段接着mid继续走，整个过程是确定性的连续动作，不存在“两个方案竞争同一个位置”的情况。所以收益用加法，这是很多题解里一笔带过、但理解不透会写错的关键点。
2.3 两张表的对照关系
| 表名 | 含义 | 第0列来源 | 递推公式 |
|---|---|---|---|
| jump[i][k] | 取2^k段后的指针位置 | 最优段终点 + 1 | jump[i][k] = jump[jump[i][k-1]][k-1] |
| val[i][k] | 取2^k段的累计最大收益 | 段内价值最大值 | val[i][k] = val[i][k-1] + val[jump[i][k-1]][k-1] |
你发现没有，两张表实际上是同一套“二进制拼装逻辑”的两个输出：一个输出位置，一个输出收益。预处理的循环结构完全一样，只是在合并时一个查jump、一个查val。写代码时把这两张表放在同一个for循环里更新，既省时间又不容易漏更新。
3. 手推一个10颗宝石的样例：让转移方程“活”起来
3.1 样例设定与边界约定
光看公式容易发虚，我们拿一组具体数据手推一遍。假设项链有n = 10颗宝石，价值从左到右为：
4 1 2 3 5 2 1 4 3 2每次只能取长度为2或3的连续段，即L = 2, R = 3。目标是从第1颗出发，恰好取m = 3段，求最大总价值。
先做前缀和pre[i]，方便后面O(1)查询区间价值：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| pre[i] | 0 | 4 | 5 | 7 | 10 | 15 | 17 | 18 | 22 | 25 | 27 |
3.2 填第一列：jump[i][0]与val[i][0]
站在位置1，可选终点只有2（拿第1、2颗，价值4+1=5）和3（拿第1、2、3颗，价值4+1+2=7），取最大，bestEnd = 3，bestVal = 7，所以jump[1][0] = 4，val[1][0] = 7。
按同样的规则把前9个位置算一遍，得到下表：
| i | 候选终点范围 | 最优终点 | jump[i][0] | val[i][0] |
|---|---|---|---|---|
| 1 | 2 ~ 3 | 3 | 4 | 7 |
| 2 | 3 ~ 4 | 4 | 5 | 6 |
| 3 | 4 ~ 5 | 5 | 6 | 10 |
| 4 | 5 ~ 6 | 6 | 7 | 10 |
| 5 | 6 ~ 7 | 7 | 8 | 8 |
| 6 | 7 ~ 8 | 8 | 9 | 7 |
| 7 | 8 ~ 9 | 9 | 10 | 8 |
| 8 | 9 ~ 10 | 10 | 11 | 9 |
| 9 | 10 ~ 11 | 11 | 12 | 9 |
注意看i = 9那行，候选终点已经出现11号位置，这就是环形复制数组发挥作用的地方——11号位置对应原项链第1颗的复制品。如果没有2n的数组空间，这里就得写特判了。
3.3 填第二列：把两段拼成一段
现在算jump[i][1]和val[i][1]，代表“连续取2段”。以i = 1为例：
- 第一段从1出发，end在3，收益7，停在4；
- 第二段从4出发，查表jump[4][0] = 7，收益val[4][0] = 10；
- 合并结果：jump[1][1] = 7，val[1][1] = 7 + 10 = 17。
把前6个位置都算出来：
| i | jump[i][1] | val[i][1] |
|---|---|---|
| 1 | 7 | 17 |
| 2 | 8 | 14 |
| 3 | 9 | 17 |
| 4 | 10 | 18 |
| 5 | 11 | 17 |
| 6 | 12 | 16 |
如果你愿意，继续填第三列也行，但思路完全一样：jump[1][2] = jump[7][1]，val[1][2] = val[1][1] + val[7][1]。实际代码里用一个双层循环就一次性填完了，这里就不再手算到底。
3.4 查询阶段：把m拆成二进制
目标m = 3，二进制是2 + 1。查询过程如下：
- 先处理2这一位：ans += val[1][1] = 17，指针从1跳到jump[1][1] = 7；
- 再处理1这一位：ans += val[7][0] = 8，指针跳到jump[7][0] = 10；
- 总收益 = 17 + 8 = 25。
对应的三段分别是：第1~3颗（4+1+2=7）、第4~6颗（3+5+2=10）、第7~9颗（1+4+3=8），三段互不重叠，总价值25。这个结果用手工枚举也能验证，但用倍增表只查了两次表就拿到了答案，效率差距一目了然。
4. 完整实现与复杂度分析：代码里的每行都要有说法
4.1 主流程代码
下面给出这道题的核心实现。为了把注意力集中在算法上，我没有写文件读写和多组数据的处理，洛谷提交时按题目的输入格式稍作调整即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; const int LOG = 18; int n, L, R, m; ll a[MAXN * 2], pre[MAXN * 2]; int jump[MAXN * 2][LOG]; ll val[MAXN * 2][LOG]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> L >> R >> m; for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i + n] = a[i]; // 环形复制 } for (int i = 1; i <= 2 * n; ++i) { pre[i] = pre[i - 1] + a[i]; } // 第0列：每个位置选一段的最优终点和最优收益 for (int i = 1; i <= 2 * n; ++i) { int tl = i + L - 1; int tr = min(i + R - 1, 2 * n); if (tl > tr) { jump[i][0] = 0; val[i][0] = LLONG_MIN / 4; continue; } ll best = LLONG_MIN; int bestEnd = -1; for (int t = tl; t <= tr; ++t) { ll cur = pre[t] - pre[i - 1]; if (cur > best) { best = cur; bestEnd = t; } } jump[i][0] = bestEnd + 1; val[i][0] = best; } // 倍增合并 for (int k = 1; k < LOG; ++k) { for (int i = 1; i <= 2 * n; ++i) { int mid = jump[i][k - 1]; if (mid == 0 || mid > 2 * n) { jump[i][k] = 0; val[i][k] = LLONG_MIN / 4; } else { jump[i][k] = jump[mid][k - 1]; val[i][k] = val[i][k - 1] + val[mid][k - 1]; } } } // 查询：二进制拆位 int now = 1; int left = m; ll ans = 0; for (int k = LOG - 1; k >= 0; --k) { if (left >= (1 << k)) { if (jump[now][k] == 0 || jump[now][k] > 2 * n) { cout << -1 << '\n'; return 0; } ans += val[now][k]; now = jump[now][k]; left -= (1 << k); } } cout << ans << '\n'; return 0; }4.2 复杂度与常数分析
预处理部分是两层循环，外层k从1到LOG-1，内层i从1到2n，理论复杂度O(n log m)。第0列的计算里，每个位置枚举t的次数是R-L+1次，如果区间跨度大（比如L=1, R=n），这一列会变成O(n×R)，需要额外用滑动窗口或者RMQ优化。GESP八级的题一般不会在这卡你，但如果你追求稳，可以用一个长度固定的滑动窗口来求“区间内前缀和最大值”，把第0列也降到O(n)。
查询部分是O(log m)。总体复杂度在任何数据范围下都不慌，代码里数组开到2*MAXN、LOG取18，已经能覆盖绝大多数场景。如果m特别大或者n特别大，把LOG调整到20或更高即可。
4.3 为什么查询要从大到小拆位
很多初学倍增的选手习惯从小到大枚举二进制位，比如先处理1，再处理2，再处理4。这在“每个位只能选一次”的场景下会有问题——如果先处理小的位，后面遇到大的位时，已经累加的答案无法“撤回”。从大到小拆位的本质是贪心：在当前位置，能走一步大的就先走，因为倍增表里的每个jump[now][k]都已经包含了从now出发连续2^k步的全部信息，走完这个大步之后，剩余步数left一定小于2^k，不会存在重复计数。
这个“从大到小”的顺序在LCA、快速幂、倍增DP里都是同一个道理，建议直接形成肌肉记忆。
5. 考场上的三个真实翻车点：这些坑我全踩过
5.1 并列最优终点时没固定规则，导致后续状态错乱
计算第0列时，如果两个候选终点的价值一样大，比如pre[t1] - pre[i-1]等于pre[t2] - pre[i-1]，你用if (cur > best)和用if (cur >= best)得到的最优终点可能不同。这本身不影响当前这一步的价值，但会改变jump[i][0]，进而影响后面所有的jump和val合并结果。
我在本地测试时遇到过一种诡异情况：单步查询答案正确，m=2也正确，m=3就开始错。查了半天，最后发现是最优终点并列时，取前一个和后一个导致后续路径不同。解决办法很简单：并列时固定取编号更小的终点，保证任意时刻同一个i的jump[i][0]只有唯一确定值。这个细节在写if (cur > best)而非if (cur >= best)时就顺手解决了，但很多人根本不注意。
5.2 数组长度只开到n，跨过剪口的跳转直接越界
环形复制数组用2n空间，这几乎是本类题目的标配。但有些选手图省事，只开到n，然后在查询里看到jump[now][k]很大就蒙了。我建议从一开始就把数组长度统一写成MAXN * 2，前缀和、jump表、val表全部按2n处理，不要试图用取模运算替代。取模在单点访问时好用，但在倍增表这种需要连续下标递增的场景里，一旦出现“位置从n跳到1附近”就会让表的结构变混乱，得不偿失。
5.3 m大于环上可容纳段数时，查询会跳到非法位置
如果L=2，n=10，最多只能取5段；如果题目给的m=8，那必然无解。我的代码里在查询循环中检查了jump[now][k] > 2 * n，这能兜住一部分非法情况。但还有个隐藏问题：当m恰好等于可容纳段数上限时，最后一段可能把指针推得离起点特别远，如果终点正好落在2n的边界上，后续再接一段就会触发无解判断。
我的建议是，如果题目明确保证有解，不写检查也没问题；如果不保证，就把查询时的检查写完整，并且在预处理第0列时，让i + R - 1的最小值和2n取min，避免构造出不存在的段。考场上的容错率永远比代码“看起来严谨”更重要。
6. 从这道题看GESP八级的命题套路：倍增不是孤立考点
GESP八级的大纲里，倍增通常和动态规划、图论、字符串处理组合出现。像P14924这样把倍增和线性DP绑在一起考，已经是八级比较典型的出题方式。它的设计逻辑是：单纯考倍增，选手背一套LCA模板就过了；单纯考线性DP，题又太直白。只有把“单步动作抽象”和“二进制跳转合并”揉在一起，才能真正区分“背过模板”和“理解底层思想”的选手。
备考八级时，建议把近几年洛谷上的倍增相关题单刷一遍，尤其注意三类组合：
- 倍增 + 线性DP：本题就是代表，特征是“每次最多向前走固定步数，问若干步后的最优价值/最小代价”。
- 倍增 + 图论：比如在基环树上跳转、在DAG上走固定步数，跳转函数变成了图上的边。
- 倍增 + 区间查询：本质是RMQ的推广，用倍增表把区间信息合并成可累加的形式。
刷题时不要只满足于AC，每道题都问自己三个问题：单步操作怎么抽象成跳转函数？两个半段合并时需不需要额外维护信息？查询的二进制拆位是否覆盖了所有边界情况？这三个问题想清楚，八级里任何“倍增+DP”风格的题都能稳稳拿下。
这道题最让我觉得有价值的地方，是它把“环上分段”这个看起来复杂的模型，用两张倍增表拆解得干干净净。如果你正在备考八级，建议自己把样例扩展成n更大、L和R更极端的情况，再用暴力程序对拍验证倍增表的正确性。“对拍”这一步花不了十分钟，但能帮你把推导中的隐性假设全部暴露出来。我个人刷题的经验是：像这种综合型DP题，靠眼睛看永远看不出边界问题，只有让暴力和倍增收到的答案逐一对上，才敢在考场上放心地把代码交上去。
