企业官网建设流程全解析

GESP八级这次的编程题《宝石项链》，考完群里就炸了。不是因为它超纲，而是题目包装得太“项链”了，很多人一看到就往字符串匹配、图论甚至组合数学上想，结果绕了远路。实际上，这道2025年12月的C++八级真题，核心是一套非常标准的C++竞赛组合拳：数组倍增、双指针、前缀和、单调队列。这篇文章我用回忆版题面做底，把整道题从读题到AC的完整推导过程写下来，包括考场上的坑和调试经验，希望给后面备考八级的同学提供一份能直接参考的完整笔记。

1. 真题回顾与考点拆解

1.1 回忆版题面

先说明一下，这里用的是网上流传的回忆版题面，个别措辞可能有出入，但核心题意和数据范围基本一致。题目大意如下：

有一条由 n 颗宝石组成的环形项链，宝石按顺时针编号为 1 到 n。第 i 颗宝石有一个颜色 c_i 和一个魅力值 w_i。现在可以沿着项链剪一刀，把它变成一条链，然后从这条链上取一段连续宝石带走。要求取出的这一段中不能出现两颗颜色相同的宝石。当然，也可以选择什么都不带走。问能带走的最大魅力值总和是多少。

输入格式：第一行一个整数 n；第二行 n 个整数 c_1 到 c_n；第三行 n 个整数 w_1 到 w_n。

数据范围：1 ≤ n ≤ 5×10^5；1 ≤ c_i ≤ n；|w_i| ≤ 10^9。

输出要求：一个整数，表示最大魅力值总和。如果最优选择是什么都不带走，输出 0。

这里有个关键细节：题目要求“不能出现两颗颜色相同的宝石”，也就是说取出的子段里每种颜色最多出现一次。这个限制条件非常强，它直接决定了题目的解法，而不是单纯的无重复字符最长子串那种入门题。

1.2 考点地图：这不是一道简单的模拟题

这道题表面上是“项链”“颜色”“魅力值”，实际考的是一组在C++算法竞赛里很常见的组合：

为什么数据范围 n ≤ 5×10^5？因为这意味着 O(n log n) 勉强能过，O(n²) 必死。而上述五个知识点拼起来正好是 O(n) 的做法。所以这道题并不是在考某一个单独的算法，而是考“能不能把几个基础算法组合起来解决看似复杂的问题”。这也是GESP八级和前面几级最大的区别：七级可能还在考单点算法，八级喜欢考算法之间的嵌套和变形。

2. 从暴力到最优：思路是怎么长出来的

2.1 暴力枚举为什么不可行

先看最简单的想法：枚举一个起点和一个终点，检查这段区间内是否有重复颜色，如果没有就计算区间和，取最大值。环也容易处理，跳过头尾交界处就行。

这样的枚举复杂度是 O(n³)，因为检查重复还需要一层循环。就算用两个 for 枚举起终点，复杂度也至少是 O(n²)。n 是 5×10^5，O(n²) 大约是 2.5×10^11 次操作，在C++里跑完需要几十秒甚至几分钟，考场上绝对不可能通过。

所以我们必须找规律。规律来自哪里？来自“每种颜色最多出现一次”这个限制。

2.2 双指针的触发条件：重复颜色的“单调性”

假设我们从左到右扫描数组，维护一个窗口 [L, R]，保证窗口内所有颜色都不相同。当扫描到新的位置 R+1 时，如果它的颜色在窗口里已经出现过一次，会发生什么？

比如窗口是 [2, 7]，颜色分别是 A B C D E F，现在 R+1 位置的颜色是 C。因为 C 已经在窗口里出现过，那么任何左端点如果还在原来位置 C 第一次出现的位置左边，都会导致区间里同时包含两个 C，不合法。所以左端点 L 必须往右移动到“上一次 C 出现的位置 + 1”之后。

这就是双指针（滑动窗口）能用的核心原因：随着右端点不断右移，左端点只会向右移动，不会向左移动。这个“单调性”让我们可以用 O(n) 的时间维护所有合法窗口。如果限制条件不是“颜色不能重复”，而是类似“区间内元素个数不超过 k”，双指针也依然成立，因为左端点的约束同样是单调的。

2.3 最大价值不是最长区间：前缀和的最低点

如果这道题问的是“最长合法区间长度”，那双指针就可以直接解决：每次右移右端点，同时调整左端点，统计窗口长度最大值即可。但它问的是“最大魅力值总和”，这就多了一层问题。

对于固定的右端点 R，左端点的合法范围是连续的，比如 [L, R]。在这个范围内，任意左端点对应的区间都满足颜色互异条件。那么我们要找的其实就是区间和的最大值：

sum(L0, R) = pre[R + 1] - pre[L0]，其中 L0 ∈ [L, R]。

这里 pre 是前缀和数组。要最大化这个差值，在 pre[R+1] 固定的情况下，只需要最小化 pre[L0]。也就是说，对于每个右端点，我们想找的是合法左端点集合里前缀和最小的那个位置。

这就是“前缀和 + 区间最小值查询”的问题。为什么不是直接找最短或最长区间？因为价值有正有负。可能最长的合法区间里有很大的负值，反而不如短一点的区间。只有通过前缀和的最低点，才能同时把正负价值都考虑进去。

2.4 为什么要用单调队列

现在问题变成了：在动态变化的一个区间 [L, R] 里，查询 pre 数组的最小值。因为 L 和 R 都是单调递增的，我们可以在扫描过程中用单调队列维护。

单调队列里保存的是候选左端点的下标，并且按照 pre 值单调递增。队首总是当前窗口内 pre 最小的下标。当左端点 L 变大时，把队列中所有小于 L 的下标弹出；当新的右端点 R 加入时，把 pre[R+1] 作为下一轮左端点候选插入队尾，并且维护队尾的单调性。

这里可能有人会问：用线段树或 ST 表也能查询区间最小值，为什么非要用单调队列？因为线段树是 O(log n) 每个查询，总复杂度 O(n log n)，对于 5×10^5 的数据理论上也能过，但代码复杂度明显更高。而单调队列配合双指针是 O(1) 平摊，不仅常数小，更重要的是代码简洁，不容易在紧张环境下写错。在考场上，能 O(n) 就别 O(n log n)，这是我一直坚持的点。

2.5 环形项链的数组倍增处理

项链是环形的，这意味着可取区间可能横跨原数组的末尾和开头，比如取最后两颗和第一颗。处理环形连续区间最经典的做法就是“数组倍增”：把原数组复制一份接在后面，得到长度 2n 的数组。

为什么这样可行？因为原环上任意一段连续区间，长度最多是 n（因为每颗宝石最多取一次）。在长度 2n 的数组里，一定存在一个从某个起点开始、长度不超过 n 的区间和它一一对应。我们只需要枚举复制数组里所有左端点和右端点，只要窗口长度不超过 n，就不会出现“同一颗宝石被取两次”的情况。

倍增之后，双指针的右端点可以一直扫到 2n-1，左端点最多到 n-1。这样可以覆盖所有跨越边界的情况，同时又不会漏掉普通区间。需要注意的是，由于颜色互异的限制，合法窗口长度天然不会超过颜色种类数，而 c_i 的范围正好是 1 到 n，所以长度限制其实是自然满足的。不过写上长度限制代码更稳，后面会细说。

3. 核心算法与逐段解释

3.1 变量定义与读入

先梳理需要的变量：

• color：倍增后的颜色数组，长度 2n。
• val：倍增后的价值数组，长度 2n，注意用 long long。
• pre：前缀和数组，长度 2n+1。
• cnt：记录当前窗口内每种颜色出现的次数，因为颜色范围是 1~n，数组开 n+1 即可。
• last：记录当前窗口中每种颜色最近一次出现的下标，用来快速找到重复位置。
• head / tail / q：手写单调队列，q 里存的是 pre 数组的下标。

为什么要手写队列而不是用 std::deque？因为手写数组队列常数更小，在 5×10^5 的数据下更稳。而且这种单调队列模板在八级考场上是应该背下来的。

读入的时候先读颜色，再读价值。注意题目给的顺序是颜色一行，价值一行，不要顺拐了。我见过不少同学把两个输入顺序搞反，后面所有输出都错位。

3.2 前缀和的计算

前缀和数组 pre 长度为 2n+1，pre[0] = 0，pre[i] 表示倍增后数组前 i 个元素的和。计算很简单：

for (int i = 0; i < 2 * n; i++) { pre[i + 1] = pre[i] + val[i]; }

这里的 pre[i] 对应的意义是：如果左端点是 i，那么区间 [i, R] 的和就是 pre[R+1] - pre[i]。所以 pre 数组的下标代表左端点位置。这一点心里要清楚，否则后面写单调队列时很容易index错位。

3.3 窗口维护的三种情况

扫描右端点 R 时，遇到颜色 col = color[R]，分三种情况处理。

第一种，cnt[col] == 0，说明 col 还没在窗口中出现，直接把它加入窗口，cnt[col]++，last[col] = R。

第二种，cnt[col] > 0，说明窗口里已经有这个颜色，而且它的位置是 last[col]。此时必须把左端点 L 移到 last[col]+1，同时把从原 L 到 last[col] 之间所有颜色从窗口计数里删掉。代码是这样：

while (L <= pos) { cnt[color[L]]--; L++; }

这里要注意，因为窗口是连续区间，从原 L 到 pos 之间的所有颜色都必须“出窗口”，不只是把 col 的计数减掉。这一步如果漏掉了，后续 cnt 数组就会失真，窗口颜色互异的判断也会挂。

第三种，虽然颜色不重复，但窗口长度可能超过 n。前面说过，因为颜色互异限制，这种情况在本题里几乎不会出现，但为了保险还是写一个 while：

while (R - L + 1 > n) { cnt[color[L]]--; L++; }

如果哪天你把这题的“颜色互异”改成“最多允许出现两次”，这个长度限制就会变得必不可少。写代码时多这一层保护，不会吃亏。

3.4 单调队列的完整逻辑

单调队列在代码里的位置很讲究。每到一个新的右端点 R，要先完成窗口调整，再查询以 R 为右端点的最优解，然后把 R+1 作为下一轮的左端点候选插入队尾。

具体流程：

初始化时队列里只有 0，也就是 pre[0]，对应左端点为 0。

每轮扫描 R：

1. 先按上面的窗口调整逻辑更新 L。
2. 把队列头部所有小于 L 的下标弹出。因为这些下标已经不在合法左端点范围内了。
3. 用队首计算答案：ans = max(ans, pre[R+1] - pre[q[head]])。
4. 把 pre[R+1] 插入队列，同时维护队尾单调递增。如果队尾 pre 值大于等于 pre[R+1]，就弹出队尾，然后把 R+1 加进去。

为什么插入 R+1 而不是 R？因为左端点是 R 时，对应区间 [R, R]，区间和是 pre[R+1] - pre[R]，所以 pre[R] 应该在上一轮就已经插入队列了。初始队列里放的是 pre[0]，正好支撑 R=0 的查询。一轮查询完成后，把 pre[R+1] 加进去，正好为下一轮 R+1 准备左端点 R+1 的候选。这个时机问题非常容易出错，考场上有不少人在这里 index 差 1，导致答案偏大或偏小。

3.5 完整AC代码

下面给出我参考在线OJ风格整理的完整C++代码。这个版本可以直接复制到洛谷或C++17环境里测试。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> origColor(n); vector<long long> origVal(n); for (int i = 0; i < n; i++) cin >> origColor[i]; for (int i = 0; i < n; i++) cin >> origVal[i]; vector<int> color(2 * n); vector<long long> val(2 * n); for (int i = 0; i < n; i++) { color[i] = origColor[i]; color[i + n] = origColor[i]; val[i] = origVal[i]; val[i + n] = origVal[i]; } vector<long long> pre(2 * n + 1, 0); for (int i = 0; i < 2 * n; i++) { pre[i + 1] = pre[i] + val[i]; } vector<int> cnt(n + 1, 0); vector<int> last(n + 1, -1); vector<int> q(2 * n + 1); int head = 0, tail = 0; q[tail++] = 0; int L = 0; long long ans = 0; for (int R = 0; R < 2 * n; R++) { int col = color[R]; if (cnt[col] > 0) { int pos = last[col]; while (L <= pos) { cnt[color[L]]--; L++; } } cnt[col]++; last[col] = R; while (R - L + 1 > n) { cnt[color[L]]--; L++; } while (head < tail && q[head] < L) head++; ans = max(ans, pre[R + 1] - pre[q[head]]); while (head < tail && pre[q[tail - 1]] >= pre[R + 1]) tail--; q[tail++] = R + 1; } cout << ans << '\n'; return 0; }

这段代码里，单调队列长度直接开 2n+1，因为队列里最多会插入 2n 个下标，不会越界。head 和 tail 手动维护，省掉了 std::deque 的动态内存开销。

3.6 几个容易被忽略的细节

第一个细节是 ans 的初始值。题目允许什么都不带走，所以 ans 初始为 0。如果题目要求必须带走一段非空区间，就得另当别论，可能要把 ans 初始化为 LLONG_MIN，然后单独处理全负的情况。但本题允许空段，0 是最简单的选择。

第二个细节是 last 数组的更新。last[col] 记录的是 col 在当前窗口内最近一次出现的下标。在把 col 加入窗口后，一定要立刻更新 last[col] = R。如果漏了，下一次遇到同色时，pos 会指向旧位置，左端点会移动错误。

第三个细节是倍增后扫到 2n 的边界。因为 R 最大是 2n-1，而窗口长度不会超过 n，所以左端点 L 最多是 n-1。q 数组的长度开 2n+1 完全够用。千万不要把 R 往 2n 再推一位，pre 数组会越界。

第四个细节是颜色压缩。虽然题目给出 c_i ≤ n，但如果数据范围不友好，c_i 可能很大，比如 10^9。这时需要离散化，把每个颜色映射到 1~n 的编号。离散化方法很简单：读入到临时数组后排序去重，再用 lower_bound 映射。但如果题目明确说了 c_i ≤ n，就不需要这一步。

4. 常见错误与排查实录

4.1 常见运行错误

运行错误里最常见的是数组越界。很多人把 color、val、pre 开成 2n，但 pre 需要 2n+1，因为 pre[2n] 会被访问到。还有一个隐蔽的地方：q 数组长度是 2n+1，但如果队列里插入的下标多了一个，就会越界。我在考场上习惯把队列数组直接开成 2n+5，多一点冗余，反正内存不是问题。

另一个运行错误是 cnt 数组开小了。题目颜色范围是 1~n，但如果不小心复制数组后颜色编号没处理，可能访问到 cnt 越界。建议在写代码前先声明“c_i 范围 1~n”，把 cnt 和 last 都开成 n+2，宁可多开一点。

4.2 逻辑错误

最容易挂的逻辑错误就是队列弹出时机。如果把“弹出过期左端点”放在“查询答案”之后，会导致队首可能是已经不合法的前缀和最小值，答案被算大。比如窗口左边界已经移动到 5，但队列里还留着下标 2 的 pre，查询到它的 pre 很小，算出一个非常大的假答案。

我在调这种错时，会在输出答案前打印 L、R、head、tail、q[head] 这几个值，肉眼对照一遍就清楚了。

第二个逻辑错误是窗口长度限制的位置。有些同学在每次右移后都检查长度，但忘了在颜色重复时先处理重复，导致先超长再缩窗口，缩完之后可能把刚加入的颜色也缩掉。正确顺序应该是：先处理重复颜色，再处理长度，最后查询。我自己试过把顺序反过来，样例过了，大数据就挂，后来才发现是顺序问题。

4.3 随机对拍脚本思路

对这种数据密集型题目，考场上最可靠的方式是写一个暴力解法做对拍。暴力可以很简单：枚举所有起点和终点，检查区间内颜色是否重复，计算区间和，取最大值。n 小时可以随便跑。

我常用的对拍结构是：写两个程序，一个 AC 版一个暴力版，再写一个随机数据生成器，循环跑几百次，每次比较两个程序的输出。生成器要随机化颜色和价值，不要把 n 设太小，20 到 100 之间就能暴露大量边界问题。还要专门生成一些极端数据：全部颜色相同、所有价值为负、一条完整环颜色全部不同、价值全为 1e9 等。

4.4 考场上的调试技巧

GESP 考场环境不一定支持在线调试，所以更依赖肉眼检查和输出中间变量。一个技巧是加一个 debug 开关，平时注释掉，需要调试时打开，打印 R、L、cnt 数组、队列内容。打印队列可以用一个循环从 head 到 tail-1 输出所有下标和 pre 值，这样能直接看出单调队列有没有失效。

还有一个技巧：小样例。如果题目给的样例只有 5 颗宝石，手工模拟一遍就能覆盖多数情况。但某些边界问题需要自己构造最小样例，比如 n=1、n=2、n=3 带正负值的情况。n=1 的时候，复制数组长度是 2，窗口可能取第一颗或第二颗，答案应该是 max(0, w[1])。我经常在 n=1 上抓到 border 问题。

4.5 错误速查表

5. 从这道题看八级备考和考场策略

5.1 八级核心算法方向

GESP C++ 八级的考点范围很广，包括树状数组、线段树、背包DP、状态压缩、最短路、最小生成树，以及一些组合数学基础。但很多题目其实都围绕几个高频算法展开：滑动窗口、前缀和、二分、单调队列、树状数组、基础DP。

《宝石项链》这题之所以有代表性，是因为它把“数据结构优化”和“窗口维护”结合在了一个看似生活化的场景里。八级的真题往往有一个特点：题目描述不吓人，姿势也不偏，偏的是组合方式和边界处理。所以备考时不要只刷单个算法模板，要多练“模板缝合题”，比如双指针套前缀和、树状数组套二分、DP套单调队列优化。

另外，C++ 本身的基础要非常扎实。八级要求对 STL 很熟，比如 vector、unordered_map、priority_queue，但有时手写数组反而更稳。像这题的手写单调队列，代码量并不大，如果临时去用 std::deque，也完全没问题，但手写更符合竞赛习惯。

5.2 考场上如何识别“滑动窗口+单调队列”这道题

识别这个套路有几个信号：

第一，问题涉及连续子数组或连续子段。出现“连续”两个字，就要警惕前缀和、双指针、单调队列这一套。

第二，有某种“窗口合法性”限制，比如颜色不重复、数字不重复、区间和不超过某个阈值。只要限制条件随着右端点右移而单调成立，双指针就是第一候选。

第三，求的不是“最大长度”而是“最大和”或“最小和”，这时候双指针只能确定合法区间，还要再嵌套一个能查区间极值的数据结构。如果左右端点都单调，那就是单调队列。

第四，数据范围 n 在 10^5 到 10^6 之间，并且要求 O(n)。如果 n 到 10^5，O(n log n) 也能过，很多人在考场上会选择线段树，虽然能过，但不如单调队列拿得更稳。

5.3 备考建议

针对这道题带出来的知识点，我的建议是：把“数组倍增 + 双指针 + 前缀和 + 单调队列”当作一个组合模板背熟。暴力做好对拍，确保边界完全可靠。平时刷题时多关注 C++ 里 long long 的使用习惯，只要 w_i 绝对值超过 2×10^9，一律用 long long，不要纠结。

还有一点，GESP 八级命题近年来越来越喜欢出“模拟背景 + 算法内核”的题，背景可能很花哨，但拆出模型后就是一个经典套路。所以读题时先别管宝石项链好不好看，先在草稿纸上写出核心限制条件和目标函数，把“取一段连续宝石”翻译成“找一个合法子区间”，把“最大魅力值”翻译成“最大子段和”，模型就一下子清楚了。

我个人在考场上写这类题，习惯先把数组倍增、双指针、前缀和、单调队列四个模块分别注释清再合起来写，每一步都跑一个小样例验证。尤其是最后那个入队时机，是真容易错。如果你也想拿这道题练手，建议先自己写一遍，再和我给的代码对照，重点看队列维护部分的顺序。写通这道题，八级里很多关于连续区间和最优解的题目，你都会有底气多了。