把环复制一倍,用双指针求出"从每个位置出发、最短的含全部 m 种宝石的窗口",再用倍增数出每个起点最多能切几段:前 k − 1 段都取最短窗口,最后一段把剩下的整块兜住。
对应的选择、判断题: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ₙ,表示每枚宝石的种类。
输出一行,一个整数,表示宝石项链最多可以划分的段数。
6 2 1 2 1 2 1 2
输出:
3
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ₙ 中出现。
[s, e],而最短窗口的右端 nxt[s] ≤ e。把第一段改短成 [s, nxt[s]],剩下的宝石只多不少,原来的后续划分照样放得下——这就是标准的交换论证;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 种宝石 |
[s, e],而最短窗口的右端是 nxt[s] ≤ e。把第一段改短成 [s, nxt[s]],后面剩下的宝石只多不少,原来的分法照样能用——所以"取最短"不会让段数变少k − 1 段取最短,最后一段就把剩下的 [p, s + n − 1] 整块兜住;它是"最短窗口 [p, nxt[p]]"的超集,超集当然也含全部 m 种。s + n,就有 k 段可行——不需要"恰好落在 s + n 上"。nxt[i] 关于 i 单调不减,所以"跳 2ʲ 段后的位置"也是单调的,可以像求 LCA 那样先大步跳、再小步逼近项链为 1 2 1 2 1 2,复制一倍后是 1 2 1 2 1 2 | 1 2 1 2 1 2。先求最短窗口 nxt[i](从 i 出发、第一次凑齐两种宝石的位置):
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| nxt[i] | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
相邻两枚宝石的种类必然不同(交替出现)
所以从 i 起只要取 [i, i + 1] 就凑齐了两种
这就是最短窗口,长度恰好 2
✅ 每段最短长度 = 2
第 1 段:[1, 2](含 1、2 两种)→ 下一段起点 3
第 2 段:[3, 4] → 下一段起点 5
第 3 段:[5, 6] → 下一段起点 7
第 4 段要的最短窗口是 [7, 8],已经越过整圈右端 6 → 停
所以最多 3 段(最后一段 [5, 6] 本身就是最短窗口)
✅ 可行 3 段
s = 2:[2, 3]、[4, 5]、[6, 7],也恰好 3 段
s = 3、4、5、6 同理,都是 3 段
6 枚宝石、每段至少 2 枚,所以 3 段就是理论上限
答案 = 3
✅ 与样例输出一致
m 枚宝石,所以段数一定 ≤ ⌊n / m⌋。⌊6 / 2⌋ = 3,而贪心恰好达到了这个上界(此时每一段恰好都是最短窗口,连"兜住"都用不上)。项链为 3 1 3 1 2 1 2,复制一倍后 3 1 3 1 2 1 2 | 3 1 3 1 2 1 2 | …。先看最短窗口(前 7 个位置):
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| nxt[i] | 5 | 5 | 5 | 8 | 8 | 8 | 9 |
| 最短窗口 | [1..5] | [2..5] | [3..5] | [4..8] | [5..8] | [6..8] | [7..9] |
再对每个起点 s 数一数"能切几段":前 k − 1 段取最短窗口,最后一段把剩下的全部兜住(右端 s + n − 1 处收尾)。
| 起点 s | 整圈右端 s + n − 1 | 取最短窗口的段 | 最后一段(兜住剩余) | 段数 |
|---|---|---|---|---|
| 1 | 7 | [1..5] | 剩余 [6..7] 只有 1、2 两种,凑不齐 → 只能整圈算 1 段 | 1 |
| 2 | 8 | [2..5] | [6..8](位置 8 就是位置 1,三种齐了) | 2 |
| 3 | 9 | [3..5] | [6..9](1、2、3、1,被"撑长"了一段) | 2 |
| 4 | 10 | [4..8] | 剩余 [9..10] 只有 1、2 两种,凑不齐 → 只能整圈算 1 段 | 1 |
| 5 | 11 | [5..8] | 剩余 [9..11] 凑不齐 3 种 → 只能整圈算 1 段 | 1 |
| 6 | 12 | [6..8] | [9..12](1、3、1、2) | 2 |
| 7 | 13 | [7..9] | [10..13](3、1、2、1,也被"撑长"了) | 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 段
第 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)
第 1 段取最短窗口 [1..5],下一段起点 6,整圈右端是 7
从 6 出发的最短窗口是 [6..8],右端 8 > 7 → 放不进整圈
换个角度:剩下的 [6..7] 是 1、2 两种,缺第三种
所以从 1 出发最多 1 段(把整圈 [1..7] 当一段,它当然含全部三种)
✅ 1 段
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——必须老老实实枚举起点、数跳跃次数,最后取最大。双指针一次求出所有 nxt,再用二进制提升数出"从每个起点最多能切几段"(前 k − 1 段取最短窗口,最后一段兜住剩下的)
≤ s + n 比较f(i) = nxt[i] + 1 单调不减(窗口右端随起点右移而不减),所以 f 的任意次复合也单调——这正是"数出最大的 k 使 fᵏ(s) ≤ s + n"能这么写的根本原因。对起点 s 反复 p ← nxt[p] + 1,数出"跳完不越界"的次数
m 枚,所以 n 个起点合计要跳约 n / m × n 次。| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 双指针 + 倍增 | O(n log n) ≈ 2 × 10⁶ | 约 50 行 ✅ 推荐 |
| 每个起点直接模拟跳 | O(n²) = 10¹⁰ | 约 40 行 ❌ 超时 |
| 二分段数 + 贪心校验 | O(n log² n) 起,正确性还更难证 | 约 80 行 ⚠️ 不推荐 |
第一行输入 n m;第二行输入 n 个宝石种类(1…m,且每种至少出现一次)。程序会先算出每个位置的最短窗口 nxt,再对每个起点数出最多能切几段,并列出每一段的区间。演示规模取 n ≤ 12。
点按钮开始 →
#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。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 2 | 3 | 题面样例 1:每两枚一段,达到上界 ⌊6/2⌋ |
7 3 | 2 | 题面样例 2:s = 2、3、6、7 能 2 段,其中 s = 3、7 靠"最后一段撑长" |
2 2 | 1 | 最小规模:两枚一段,正好一段 |
4 2 | 2 | 偶数长度交替串:每两枚一段 |
6 3 | 2 | 三种宝石各出现两次,每段至少 3 枚 → 最多 2 段 |
8 2 | 4 | 每段 2 枚 → 4 段,再次达到上界 |
6 2 | 3 | 起点必须选对:s = 2、4、6 拿到 3 段,s = 1、3、5 只有 2 段 |
10 3 | 2 | 上界 ⌊10/3⌋ = 3 取不到:真实答案是 2 |
9 3 | 3 | 每段恰好 3 枚 → 3 段,验证"对齐"的重要性 |
100000 2 交替串 | 运行验证 | 最大规模,考察双指针 + 倍增是否跑得动 |
nxt 是"最短"窗口吗?③ 判据是"不超过 s + n"吗?④ 答案下界给了 1 吗?⌊n / m⌋,所以 LOG 要开到 17 以上。nxt[i] 时要把 i 移出窗口,否则后续全错。nxt:rr 只增不减,整轮 O(n)LOG × 2n ≈ 18 × 2 × 10⁵ = 3.6 × 10⁶ 次赋值LOG = 18 次比较,n 个起点共约 1.8 × 10⁶2 × 10⁶ ~ 5 × 10⁶ 次基础操作nxt 开 2n,倍增表 up[18][2n] 约 18 × 2 × 10⁵ = 3.6 × 10⁶ 个 int,约 14 MB,在 256 MB 限制内很宽裕;种类计数器 cnt 只需 O(m)。
✅ 百万量级的操作配上很松的常数,1 秒时限轻松通过。本题两个难点都不在"写麻烦",而在"想清楚":为什么前 k − 1 段取最短就够、为什么判据是"不超过"而不是"恰好等于"。
// 「破环成链 + 最短窗口 + 倍增」通用骨架 // 适用场景:环形数组上要划分/统计"连续且满足某性质"的块 // 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 段取最短"由"改短后剩余更多"证得最优 | 所有"最大分段数 / 最少使用次数"类贪心 |
| 二进制提升 | 单调跳跃函数用倍增一次跳一大截 | 祖先查询、跳跃游戏、区间覆盖的最少步数 |