GESP 题解库 / 8 级题解 / [GESP202512 八级] 宝石项链 · 第 3 / 24 题
GESP202512 八级 · P14924 · 困难

宝石项链

把环复制一倍,用双指针求出"从每个位置出发、最短的含全部 m 种宝石的窗口",再用倍增数出每个起点最多能切几段:前 k − 1 段都取最短窗口,最后一段把剩下的整块兜住。

💎
n ≤ 10⁵
宝石枚数
🌈
2 ≤ m ≤ n
宝石种类数
⚡
O(n log n)
双指针 + 倍增
🎯
最短窗口 + 倍增跳跃
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

对应的选择、判断题:https://ti.luogu.com.cn/problemset/1204

题目描述

小 A 有一串包含 n 枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以 1, 2, …, n 编号,第 n 枚宝石与第 1 枚宝石相邻。项链由 m 种宝石组成,其中第 i 枚宝石种类为 tᵢ。

小 A 想将宝石项链分给他的好朋友们。具体而言,小 A 会将项链划分为若干连续段,并且需要保证每段都包含全部 m 种宝石。请帮小 A 计算在满足条件的前提下,宝石项链最多可以划分为多少段。

输入格式

第一行,两个正整数 n, m,分别表示宝石项链中的宝石的数量与种类数。
第二行,n 个正整数 t₁, t₂, …, tₙ,表示每枚宝石的种类。

输出格式

输出一行,一个整数,表示宝石项链最多可以划分的段数。

输入输出样例 #1

6 2
1 2 1 2 1 2

输出:

3

输入输出样例 #2

7 3
3 1 3 1 2 1 2

输出:

2

说明 / 提示

对于 40% 的测试点,保证 2 ≤ n ≤ 1000。
对于所有测试点,保证 2 ≤ n ≤ 10⁵,2 ≤ m ≤ n,1 ≤ tᵢ ≤ m,保证 1, 2, …, m 均在 t₁, t₂, …, tₙ 中出现。

💡
人话翻译:一串环形项链,要剪成若干连续的段,并且每一段里 m 种宝石必须全都出现过。问最多能剪成几段。
四个关键认识:
① 为什么"每段尽量短"最优?设某个最优划分的第一段是 [s, e],而最短窗口的右端 nxt[s] ≤ e。把第一段改短成 [s, nxt[s]],剩下的宝石只多不少,原来的后续划分照样放得下——这就是标准的交换论证;
② 注意:只有"前 k − 1 段"需要取最短,最后一段是把剩下的全部兜住。它是"最短窗口"的超集,而超集当然也含全部 m 种——所以最后一段不需要恰好卡在某个位置上。
③ 为什么要把数组复制一倍?环上从任意位置起、跨过"接缝"的段,在一条直线上是看不见的,复制成 2n 之后就都变成了普通区间;
④ 为什么要用倍增?如果对每个起点都老老实实一段一段跳,最坏 O(n²) = 10¹⁰;而"跳 k 段之后的位置"关于起点单调,可以用二进制提升一次跳一大堆,单个起点降到 O(log n)。

🔍 关键词提取

环形结构复制一倍破环双指针求最短窗口贪心分段的交换论证二进制提升

已知条件

项目说明
输入第一行 n、m;第二行 n 个宝石种类 tᵢ
输出最多能划成多少段
数据范围2 ≤ n ≤ 10⁵,2 ≤ m ≤ n
种类约束1 ≤ tᵢ ≤ m,且 1 … m 每种都至少出现一次
环的性质第 n 枚与第 1 枚相邻,段可以跨过接缝
段的要求连续,且每段都必须包含全部 m 种宝石

需要解决的问题

02
思维导图
整理解题思路的全貌
💎 最短窗口 + 倍增,数出每个起点的最多段数
🧠 环形处理
把数组复制一倍成 2n
环上的连续段变成普通区间
起点只枚举 1 … n
目标:把 [s, s+n−1] 切成最多段
🪟 最短窗口
nxt[i] = 从 i 起最短含全 m 种的右端
双指针一遍 O(n)
nxt 关于 i 单调不减
只需算到 i = 2n
⏩ 倍增跳跃
f(i) = nxt[i] + 1(下一段的起点)
f 单调 ⇒ 可二进制提升
数出最大的 k 使 fᵏ(s) ≤ s + n
k 就是起点 s 能切出的最多段数
⚠️ 易错点
忘了复制一倍,环被当成断线
倍增层数不够(最多可跳 ⌊n/m⌋ 段)
误以为"最后一段也必须是最短窗口"
答案下界忘了给 1
03
样例手算推导
样例 1 与样例 2 的逐起点推演

🧮 样例 1:n = 6、m = 2,交替的两种宝石

项链为 1 2 1 2 1 2,复制一倍后是 1 2 1 2 1 2 | 1 2 1 2 1 2。先求最短窗口 nxt[i](从 i 出发、第一次凑齐两种宝石的位置):

i123456789101112
nxt[i]2345678910111213
1
为什么 nxt[i] = i + 1

相邻两枚宝石的种类必然不同(交替出现)

所以从 i 起只要取 [i, i + 1] 就凑齐了两种

这就是最短窗口,长度恰好 2

✅ 每段最短长度 = 2

2
以 s = 1 为起点贪心跳

第 1 段:[1, 2](含 1、2 两种)→ 下一段起点 3

第 2 段:[3, 4] → 下一段起点 5

第 3 段:[5, 6] → 下一段起点 7

第 4 段要的最短窗口是 [7, 8],已经越过整圈右端 6 → 停

所以最多 3 段(最后一段 [5, 6] 本身就是最短窗口)

✅ 可行 3 段

3
换个起点看看

s = 2:[2, 3]、[4, 5]、[6, 7],也恰好 3 段

s = 3、4、5、6 同理,都是 3 段

6 枚宝石、每段至少 2 枚,所以 3 段就是理论上限

答案 = 3

✅ 与样例输出一致

🔑
这道样例把"上界"讲透了:每段至少含 m 枚宝石,所以段数一定 ≤ ⌊n / m⌋。
样例 1 里 ⌊6 / 2⌋ = 3,而贪心恰好达到了这个上界(此时每一段恰好都是最短窗口,连"兜住"都用不上)。
但上界并不总能达到——下一道样例就是反例。

🧮 样例 2:n = 7、m = 3,答案为什么是 2

项链为 3 1 3 1 2 1 2,复制一倍后 3 1 3 1 2 1 2 | 3 1 3 1 2 1 2 | …。先看最短窗口(前 7 个位置):

i1234567
nxt[i]5558889
最短窗口[1..5][2..5][3..5][4..8][5..8][6..8][7..9]

再对每个起点 s 数一数"能切几段":前 k − 1 段取最短窗口,最后一段把剩下的全部兜住(右端 s + n − 1 处收尾)。

起点 s整圈右端 s + n − 1取最短窗口的段最后一段(兜住剩余)段数
17[1..5]剩余 [6..7] 只有 1、2 两种,凑不齐 → 只能整圈算 1 段1
28[2..5][6..8](位置 8 就是位置 1,三种齐了)2
39[3..5][6..9](1、2、3、1,被"撑长"了一段)2
410[4..8]剩余 [9..10] 只有 1、2 两种,凑不齐 → 只能整圈算 1 段1
511[5..8]剩余 [9..11] 凑不齐 3 种 → 只能整圈算 1 段1
612[6..8][9..12](1、3、1、2)2
713[7..9][10..13](3、1、2、1,也被"撑长"了)2
1
起点 s = 2:正好两段,最后一段刚好卡住

第 1 段取最短窗口 [2..5]:宝石 1、3、1、2 → 三种齐了

下一段起点 6;整圈右端是 8

从 6 出发的最短窗口是 [6..8],右端 8 ≤ 8 → 还能再切一段

第 2 段 [6..8]=位置 6、7、8,即 1、2、3 → 三种齐了

再往后:从 9 出发的最短窗口是 [9..12],12 > 8 → 停

✅ 2 段

2
起点 s = 3:最后一段必须"被撑长"

第 1 段取最短窗口 [3..5]:宝石 3、1、2 → 三种齐了

下一段起点 6;整圈右端是 9

从 6 出发的最短窗口 [6..8] 右端 8 ≤ 9 → 还能再切一段

但剩下的位置 9 还没被覆盖,所以第 2 段要写成 [6..9]

[6..9] 的子区间 [6..8] 已经含三种,多加一枚当然还是三种

再往后:从 10 出发的最短窗口 [10..12] 右端 12 > 9 → 停

✅ 2 段(最后一段长 4 而不是 3)

3
起点 s = 1:为什么只有 1 段

第 1 段取最短窗口 [1..5],下一段起点 6,整圈右端是 7

从 6 出发的最短窗口是 [6..8],右端 8 > 7 → 放不进整圈

换个角度:剩下的 [6..7] 是 1、2 两种,缺第三种

所以从 1 出发最多 1 段(把整圈 [1..7] 当一段,它当然含全部三种)

✅ 1 段

4
所有起点取最大

s = 2、3、6、7 能切出 2 段;s = 1、4、5 只能 1 段

上界 ⌊7 / 3⌋ = 2,恰好达到

答案 = 2

✅ 与样例输出一致

⚠️
三个最容易踩的坑,都由这道样例暴露:
① 以为"最后一段也必须是最短窗口"。那样 s = 3、s = 7 都会被误判成"不可行",答案偏小。正确理解是:最后一段把剩下的整块兜住,它天然是最短窗口的超集。
② 以为"必须恰好落在 s + n 上"。判据其实是"跳完 k 段之后的位置 ≤ s + n",是"不超过"而不是"恰好等于"。
③ 以为答案一定等于 ⌊n / m⌋。本题 ⌊7 / 3⌋ = 2 恰好达到,但上界经常取不到:例如 n = 10, m = 3, t = 3 3 2 1 3 2 2 1 1 1,⌊10 / 3⌋ = 3,而这组数据的答案只有 2——必须老老实实枚举起点、数跳跃次数,最后取最大。
04
解法对比
双指针 + 倍增 vs 每个起点模拟跳

⚔️ 解法对比

🟢 最短窗口 + 倍增(推荐) 推荐

双指针一次求出所有 nxt,再用二进制提升数出"从每个起点最多能切几段"(前 k − 1 段取最短窗口,最后一段兜住剩下的)

  • 时间 O(n log n),n = 10⁵ 时约 1.7 × 10⁶
  • 空间 O(n log n),倍增表约 18 × 2 × 10⁵
  • 代码约 50 行
  • 判据只需一次 ≤ s + n 比较
💡
为什么倍增是"顺手"的?
跳一步的函数 f(i) = nxt[i] + 1 单调不减(窗口右端随起点右移而不减),所以 f 的任意次复合也单调——这正是"数出最大的 k 使 fᵏ(s) ≤ s + n"能这么写的根本原因。

🟠 每个起点直接一段段跳

对起点 s 反复 p ← nxt[p] + 1,数出"跳完不越界"的次数

  • 思路最直白,不用倍增
  • 单起点最坏 O(n)
  • n 个起点合计 O(n²) = 10¹⁰
  • 40% 部分分(n ≤ 1000)可用
⚠️
它慢在哪:每段的长度可能只有 m 枚,所以 n 个起点合计要跳约 n / m × n 次。
把"跳跃次数"用倍增一压,单起点从 O(n) 变成 O(log n),这就是 O(n²) 与 O(n log n) 的分水岭。

📈 性能对比

方案复杂度代码量
双指针 + 倍增O(n log n) ≈ 2 × 10⁶约 50 行 ✅ 推荐
每个起点直接模拟跳O(n²) = 10¹⁰约 40 行 ❌ 超时
二分段数 + 贪心校验O(n log² n) 起,正确性还更难证约 80 行 ⚠️ 不推荐
05
算法流程图
求最短窗口 + 枚举起点倍增跳跃
开始读入 n、m 与 n 枚宝石的种类 t把 t 复制一倍(下标开到 2n,跨过"接缝"的段也能看见)双指针求 nxt[i]:从 i 出发最短的、含全部 m 种宝石的窗口右端枚举环上的起点 s = 1 … ntarget = s + n(整圈右端再往后一格,作为"还能再切一段"的分界)沿 nxt 往后跳:p ← nxt[p] + 1,每跳一次段数加一(用倍增一次跳一大截)跳到的位置 p 还在 target 以内吗?在 ✓段数加一,继续跳超过 ✗这个起点最多就这么多了用该起点的段数更新答案(最后一段把剩下的整块兜住)s 还没枚举完吗?输出最大段数(至少为 1:整圈本身一定含全部 m 种)s 加一,换下一个起点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

💎 宝石项链最多段数(最短窗口 + 倍增跳跃)

第一行输入 n m;第二行输入 n 个宝石种类(1…m,且每种至少出现一次)。程序会先算出每个位置的最短窗口 nxt,再对每个起点数出最多能切几段,并列出每一段的区间。演示规模取 n ≤ 12。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(双指针求最短窗口 + 倍增跳跃)

#include <bits/stdc++.h>
using namespace std;

int n, m;
int t[300005];                 // 复制两倍多,防止窗口越界
int nxt[200005];               // nxt[i]:从 i 出发最短的含全部 m 种的窗口右端
int cnt[100005];               // 滑动窗口计数器
int up[18][200005];            // up[j][i] = 跳 2^j 段之后所在的位置

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
    for (int i = n + 1; i <= 3 * n; i++) t[i] = t[i - n];   // 复制成 3n

    int N = 2 * n;                       // 只需要算 1 … 2n 的最短窗口
    int SENT = N + 1;                    // 哨兵:表示"已经跳出范围"
    int rr = 0, have = 0;
    for (int i = 1; i <= N; i++) {       // 双指针:窗口右端只增不减
        while (rr < 3 * n && have < m) {
            rr++;
            if (cnt[t[rr]]++ == 0) have++;
        }
        nxt[i] = (have == m ? rr : 3 * n + 1);
        if (--cnt[t[i]] == 0) have--;
    }

    const int LOG = 18;                  // 2^17 > 10^5,够跳完任何可行的段数
    for (int i = 1; i <= N + 1; i++) up[0][i] = SENT;
    for (int i = 1; i <= N; i++) {
        int v = nxt[i] + 1;              // 下一段的起点
        up[0][i] = (v <= N ? v : SENT);
    }
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i <= N + 1; i++)
            up[j][i] = up[j - 1][up[j - 1][i]];

    int ans = 1;                         // 整圈一定含全部 m 种,至少 1 段
    for (int s = 1; s <= n; s++) {
        int target = s + n, cur = s, c = 0;
        for (int j = LOG - 1; j >= 0; j--)      // 数一数"能跳几次还不越界"
            if (up[j][cur] <= target) { cur = up[j][cur]; c += (1 << j); }
        ans = max(ans, c);                      // c 就是从起点 s 能切出的最多段数
    }

    printf("%d\n", ans);
    return 0;
}
🔑
四个要点:① 数组要复制到 3n——最短窗口的右端最远可以到 i + n − 1,而 i 本身要到 2n,所以给足余量最省心;② nxt[i] 只需算到 i = 2n,因为跳跃过程中位置不会超过 2n;③ 倍增前要做"哨兵自环":up[j][SENT] = SENT,否则越界后会读到脏数据;④ 判据是 up[j][cur] ≤ target(不超过),不是 ==——最后一段会把剩下的整块兜住。

📖 关键几行怎么看

代码作用为什么这样写
for (int i = n + 1; i <= 3 * n; i++) t[i] = t[i - n];复制成 3n环上的段跨过接缝后,在直线数组上依然是连续区间
while (rr < 3 * n && have < m) { rr++; … }双指针求最短窗口rr 只增不减,所以整轮是 O(n)
if (--cnt[t[i]] == 0) have--;左端右移一格把 i 移出窗口,为下一个起点做准备
up[0][i] = (v <= N ? v : SENT);构建倍增第一层跳出范围统一记成哨兵,便于后面统一比较
if (up[j][cur] <= target) { cur = up[j][cur]; c += (1 << j); }倍增数段数先大步跳,最后得到的 c 就是最大可行段数
ans = max(ans, c);取所有起点的最大每个起点都能给出一个可行段数,取最大即答案
⚠️
五个坑:① 忘了复制一倍,跨接缝的段全看不见,答案偏小;② 倍增层数不够,段数最多可达 ⌊n / m⌋ ≤ n / 2,LOG = 18 才够;③ 把判据写成"恰好等于 s + n",会漏掉"最后一段被撑长"的可行解,答案偏小;④ 双指针忘了右移左端,后面的 nxt 会全部算错;⑤ 答案初始化为 0,整圈一定含全部 m 种,答案至少是 1。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6 2
1 2 1 2 1 2
3题面样例 1:每两枚一段,达到上界 ⌊6/2⌋
7 3
3 1 3 1 2 1 2
2题面样例 2:s = 2、3、6、7 能 2 段,其中 s = 3、7 靠"最后一段撑长"
2 2
1 2
1最小规模:两枚一段,正好一段
4 2
1 2 1 2
2偶数长度交替串:每两枚一段
6 3
1 2 3 1 2 3
2三种宝石各出现两次,每段至少 3 枚 → 最多 2 段
8 2
1 2 1 2 1 2 1 2
4每段 2 枚 → 4 段,再次达到上界
6 2
1 1 2 2 1 2
3起点必须选对:s = 2、4、6 拿到 3 段,s = 1、3、5 只有 2 段
10 3
3 3 2 1 3 2 2 1 1 1
2上界 ⌊10/3⌋ = 3 取不到:真实答案是 2
9 3
1 2 3 1 2 3 1 2 3
3每段恰好 3 枚 → 3 段,验证"对齐"的重要性
100000 2 交替串运行验证最大规模,考察双指针 + 倍增是否跑得动
✅
自查清单:① 数组复制够长了吗?② nxt 是"最短"窗口吗?③ 判据是"不超过 s + n"吗?④ 答案下界给了 1 吗?

🚨 易错点清单

⚠️
忘了复制一倍:环上跨过接缝的段在直线数组里看不见,答案会偏小。
⚠️
误以为"最后一段也必须是最短窗口":那样会漏掉"最后一段被撑长"的可行解(如样例 2 的 s = 3、7),答案偏小。
⚠️
把判据写成"恰好落在 s + n":正确判据是"不超过 s + n",写成相等会少算段数。
⚠️
倍增层数不足:段数最多约 ⌊n / m⌋,所以 LOG 要开到 17 以上。
⚠️
双指针忘了右移左端:求 nxt[i] 时要把 i 移出窗口,否则后续全错。
⚠️
答案初始化为 0:整圈一定含全部 m 种,所以答案至少是 1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n log n)
n = 10⁵ 时运算量
约 2 × 10⁶
倍增层数
LOG = 18

时间怎么算的?

空间都用在哪?

nxt 开 2n,倍增表 up[18][2n] 约 18 × 2 × 10⁵ = 3.6 × 10⁶ 个 int,约 14 MB,在 256 MB 限制内很宽裕;种类计数器 cnt 只需 O(m)。

✅ 百万量级的操作配上很松的常数,1 秒时限轻松通过。本题两个难点都不在"写麻烦",而在"想清楚":为什么前 k − 1 段取最短就够、为什么判据是"不超过"而不是"恰好等于"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「破环成链 + 最短窗口 + 倍增」通用骨架
// 适用场景:环形数组上要划分/统计"连续且满足某性质"的块

// 1) 破环:把数组复制一倍(必要时 3 倍),环上跨接缝的段就变成普通区间
for (int i = n + 1; i <= 3 * n; i++) a[i] = a[i - n];

// 2) 最短窗口:双指针,O(n) 求出"从每个 i 出发最短的合法窗口右端"
//    rr 只增不减(窗口右端关于左端单调),所以整体是线性的
int rr = 0, have = 0;
for (int i = 1; i <= 2 * n; i++) {
    while (rr < 3 * n && have < m) { rr++; add(a[rr]); }
    nxt[i] = (have == m ? rr : INF);
    del(a[i]);                       // 左端右移一格
}

// 3) 贪心划分:段数最多 <=> 前 k-1 段尽量短(交换论证)
//    令 f(i) = nxt[i] + 1(下一段的起点),f 单调不减 => 可以二进制提升
//    起点 s 的最多段数 = 最大的 k,使 f^k(s) <= s + n
//    为什么是"<=":最后一段把剩下的整块兜住,它就是最短窗口的超集

// 4) 判据是"不超过",不是"恰好相等"——写成 == 会漏掉大量可行解

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
破环成链复制一倍把环形区间变直线区间环形 DP、环形滑动窗口、环形最大子段和
双指针最短窗口"最短的合法窗口"用单调双指针一次求完所有"最短包含全部种类 / 满足阈值"的区间问题
交换论证证明贪心"前 k−1 段取最短"由"改短后剩余更多"证得最优所有"最大分段数 / 最少使用次数"类贪心
二进制提升单调跳跃函数用倍增一次跳一大截祖先查询、跳跃游戏、区间覆盖的最少步数
🌟
思考题:如果把条件从"每段包含全部 m 种"改成"每段里任意两种宝石的数量差不超过 1",整体思路还成立吗?(提示:"最短窗口"这一环仍然成立——只要"合法窗口"满足"左端右移、最短右端不减"的单调性,就能用双指针;倍增加数段数也仍然成立(跳跃函数单调)。真正要重写的是"怎么判定一个窗口是否合法"。——这就是这个套路的模式:结构不变,判定换掉。)