GESP八级真题《宝石项链》解析：双指针+前缀和+单调队列组合拳

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^51 ≤ c_i ≤ n|w_i| ≤ 10^9。输出要求一个整数表示最大魅力值总和。如果最优选择是什么都不带走输出 0。这里有个关键细节题目要求“不能出现两颗颜色相同的宝石”也就是说取出的子段里每种颜色最多出现一次。这个限制条件非常强它直接决定了题目的解法而不是单纯的无重复字符最长子串那种入门题。1.2 考点地图这不是一道简单的模拟题这道题表面上是“项链”“颜色”“魅力值”实际考的是一组在C算法竞赛里很常见的组合考点对应题目中的角色作用数组倍增环形项链把环上任意连续区间映射到线性数组上双指针 / 滑动窗口每种颜色最多出现一次维护当前合法窗口的左右边界前缀和魅力值求和把区间和转化为前缀和的差单调队列求合法区间内的最大区间和在候选左端点中快速找最优解long longw_i 绝对值可达 1e9防止 32 位整数溢出为什么数据范围 n ≤ 5×10^5因为这意味着 O(n log n) 勉强能过O(n²) 必死。而上述五个知识点拼起来正好是 O(n) 的做法。所以这道题并不是在考某一个单独的算法而是考“能不能把几个基础算法组合起来解决看似复杂的问题”。这也是GESP八级和前面几级最大的区别七级可能还在考单点算法八级喜欢考算法之间的嵌套和变形。2. 从暴力到最优思路是怎么长出来的2.1 暴力枚举为什么不可行先看最简单的想法枚举一个起点和一个终点检查这段区间内是否有重复颜色如果没有就计算区间和取最大值。环也容易处理跳过头尾交界处就行。这样的枚举复杂度是 O(n³)因为检查重复还需要一层循环。就算用两个 for 枚举起终点复杂度也至少是 O(n²)。n 是 5×10^5O(n²) 大约是 2.5×10^11 次操作在C里跑完需要几十秒甚至几分钟考场上绝对不可能通过。所以我们必须找规律。规律来自哪里来自“每种颜色最多出现一次”这个限制。2.2 双指针的触发条件重复颜色的“单调性”假设我们从左到右扫描数组维护一个窗口 [L, R]保证窗口内所有颜色都不相同。当扫描到新的位置 R1 时如果它的颜色在窗口里已经出现过一次会发生什么比如窗口是 [2, 7]颜色分别是 A B C D E F现在 R1 位置的颜色是 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[R1] 固定的情况下只需要最小化 pre[L0]。也就是说对于每个右端点我们想找的是合法左端点集合里前缀和最小的那个位置。这就是“前缀和 区间最小值查询”的问题。为什么不是直接找最短或最长区间因为价值有正有负。可能最长的合法区间里有很大的负值反而不如短一点的区间。只有通过前缀和的最低点才能同时把正负价值都考虑进去。2.4 为什么要用单调队列现在问题变成了在动态变化的一个区间 [L, R] 里查询 pre 数组的最小值。因为 L 和 R 都是单调递增的我们可以在扫描过程中用单调队列维护。单调队列里保存的是候选左端点的下标并且按照 pre 值单调递增。队首总是当前窗口内 pre 最小的下标。当左端点 L 变大时把队列中所有小于 L 的下标弹出当新的右端点 R 加入时把 pre[R1] 作为下一轮左端点候选插入队尾并且维护队尾的单调性。这里可能有人会问用线段树或 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前缀和数组长度 2n1。cnt记录当前窗口内每种颜色出现的次数因为颜色范围是 1~n数组开 n1 即可。last记录当前窗口中每种颜色最近一次出现的下标用来快速找到重复位置。head / tail / q手写单调队列q 里存的是 pre 数组的下标。为什么要手写队列而不是用 std::deque因为手写数组队列常数更小在 5×10^5 的数据下更稳。而且这种单调队列模板在八级考场上是应该背下来的。读入的时候先读颜色再读价值。注意题目给的顺序是颜色一行价值一行不要顺拐了。我见过不少同学把两个输入顺序搞反后面所有输出都错位。3.2 前缀和的计算前缀和数组 pre 长度为 2n1pre[0] 0pre[i] 表示倍增后数组前 i 个元素的和。计算很简单for (int i 0; i 2 * n; i) { pre[i 1] pre[i] val[i]; }这里的 pre[i] 对应的意义是如果左端点是 i那么区间 [i, R] 的和就是 pre[R1] - 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。前面说过因为颜色互异限制这种情况在本题里几乎不会出现但为了保险还是写一个 whilewhile (R - L 1 n) { cnt[color[L]]--; L; }如果哪天你把这题的“颜色互异”改成“最多允许出现两次”这个长度限制就会变得必不可少。写代码时多这一层保护不会吃亏。3.4 单调队列的完整逻辑单调队列在代码里的位置很讲究。每到一个新的右端点 R要先完成窗口调整再查询以 R 为右端点的最优解然后把 R1 作为下一轮的左端点候选插入队尾。具体流程初始化时队列里只有 0也就是 pre[0]对应左端点为 0。每轮扫描 R先按上面的窗口调整逻辑更新 L。把队列头部所有小于 L 的下标弹出。因为这些下标已经不在合法左端点范围内了。用队首计算答案ans max(ans, pre[R1] - pre[q[head]])。把 pre[R1] 插入队列同时维护队尾单调递增。如果队尾 pre 值大于等于 pre[R1]就弹出队尾然后把 R1 加进去。为什么插入 R1 而不是 R因为左端点是 R 时对应区间 [R, R]区间和是 pre[R1] - pre[R]所以 pre[R] 应该在上一轮就已经插入队列了。初始队列里放的是 pre[0]正好支撑 R0 的查询。一轮查询完成后把 pre[R1] 加进去正好为下一轮 R1 准备左端点 R1 的候选。这个时机问题非常容易出错考场上有不少人在这里 index 差 1导致答案偏大或偏小。3.5 完整AC代码下面给出我参考在线OJ风格整理的完整C代码。这个版本可以直接复制到洛谷或C17环境里测试。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint origColor(n); vectorlong long origVal(n); for (int i 0; i n; i) cin origColor[i]; for (int i 0; i n; i) cin origVal[i]; vectorint color(2 * n); vectorlong 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]; } vectorlong long pre(2 * n 1, 0); for (int i 0; i 2 * n; i) { pre[i 1] pre[i] val[i]; } vectorint cnt(n 1, 0); vectorint last(n 1, -1); vectorint 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; }这段代码里单调队列长度直接开 2n1因为队列里最多会插入 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 数组的长度开 2n1 完全够用。千万不要把 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 需要 2n1因为 pre[2n] 会被访问到。还有一个隐蔽的地方q 数组长度是 2n1但如果队列里插入的下标多了一个就会越界。我在考场上习惯把队列数组直接开成 2n5多一点冗余反正内存不是问题。另一个运行错误是 cnt 数组开小了。题目颜色范围是 1~n但如果不小心复制数组后颜色编号没处理可能访问到 cnt 越界。建议在写代码前先声明“c_i 范围 1~n”把 cnt 和 last 都开成 n2宁可多开一点。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 颗宝石手工模拟一遍就能覆盖多数情况。但某些边界问题需要自己构造最小样例比如 n1、n2、n3 带正负值的情况。n1 的时候复制数组长度是 2窗口可能取第一颗或第二颗答案应该是 max(0, w[1])。我经常在 n1 上抓到 border 问题。4.5 错误速查表症状可能原因修复方法输出比答案大单调队列里混入了过期左端点把弹出过期队首放在查询之前输出比答案小插入左端点时机不对确认插入的是 pre[R1]数组越界崩溃pre 开到 2n 而不是 2n1所有前缀和数组多开一个颜色判断错乱last 没更新加入颜色后立刻更新 last[col]R环上跨边界少了情况没做数组倍增复制一份原序列并扫描到 2n-1负数答案不对ans 初始为 0 但题面要求非空根据题意调整初始值和空段逻辑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^5O(n log n) 也能过很多人在考场上会选择线段树虽然能过但不如单调队列拿得更稳。5.3 备考建议针对这道题带出来的知识点我的建议是把“数组倍增 双指针 前缀和 单调队列”当作一个组合模板背熟。暴力做好对拍确保边界完全可靠。平时刷题时多关注 C 里 long long 的使用习惯只要 w_i 绝对值超过 2×10^9一律用 long long不要纠结。还有一点GESP 八级命题近年来越来越喜欢出“模拟背景 算法内核”的题背景可能很花哨但拆出模型后就是一个经典套路。所以读题时先别管宝石项链好不好看先在草稿纸上写出核心限制条件和目标函数把“取一段连续宝石”翻译成“找一个合法子区间”把“最大魅力值”翻译成“最大子段和”模型就一下子清楚了。我个人在考场上写这类题习惯先把数组倍增、双指针、前缀和、单调队列四个模块分别注释清再合起来写每一步都跑一个小样例验证。尤其是最后那个入队时机是真容易错。如果你也想拿这道题练手建议先自己写一遍再和我给的代码对照重点看队列维护部分的顺序。写通这道题八级里很多关于连续区间和最优解的题目你都会有底气多了。