宝石项链 题解

题目理解

我们有一个由 $n$ 枚宝石组成的环形项链，宝石共有 $m$ 种。现在要将项链切成若干连续段，每一段都必须包含全部 $m$ 种宝石，并且这些段要首尾相连、恰好覆盖整条项链。目标是求出最多能切成多少段。

换句话说，我们要在环上找到一种划分方案，使得每一段都是“包含所有种类的宝石”的连续区间，并且段数尽可能多。

核心贪心思想

要想让段数尽可能多，每一段都应当尽可能短。因为如果我们把某一段变长，留给后面宝石的空间就会变小，段数肯定不会增加。因此，在任何一个位置作为一段的起点，我们都会选择最短的包含全部 $m$ 种宝石的区间作为这一段，这是一种贪心策略，可以证明它是最优的。

于是问题转化为：

1. 对于环上的每个位置 $i$，求出从 $i$ 开始最短的包含所有 $m$ 种宝石的区间长度，记为 len[i]。
2. 从某个起点 $s$ 开始，反复取长度为 len[s] 的段，并将起点移动到这一段末尾的下一个位置，直到走完整条项链。这样得到的段数就是起点为 $s$ 时的最优解。
3. 因为是环形项链，起点可以是 $1 \sim n$ 中的任意一个，答案就是所有起点的结果的最大值。

步骤一：滑动窗口预处理最短合法段

由于项链是环形的，我们先将宝石序列复制一遍，变成长度为 $2n$ 的数组 $t[1\ldots 2n]$，其中 $t_{i+n}=t_i$。这样环上的任意区间都可以对应到 $2n$ 数组上的一个长度不超过 $n$ 的连续子数组。

对于每个起点 $i$（$1 \le i \le n$），我们用**双指针（滑动窗口）**求出最小的 $r$，使得区间 $[i,r]$ 包含全部 $m$ 种宝石。此时 len[i] = r - i + 1。

具体做法：

• 维护右指针 $r$，以及一个计数器 tot 表示当前窗口内已经覆盖的宝石种类数。
• 对于 $i$ 从 $1$ 到 $n$：
  • 不断右移 $r$，并将新加入的宝石计数增加，直到 tot == m。
  • 此时 len[i] = r - i + 1。
  • 然后将左端点 $i$ 移出窗口，对应宝石计数减一；如果该宝石计数变为 $0$，则 tot 减一。

因为 $r$ 只会单调右移，总复杂度 $O(n)$。

步骤二：倍增优化跳转

直接对每个起点模拟跳转，最坏需要 $O(n^2)$ 的时间（例如每一段长度都很短，需要跳很多次），不能通过 $n=10^5$ 的数据。我们需要倍增来加速。

我们定义 $jump[k][i]$：从位置 $i$ 开始，连续走 $2^k$ 段最短合法段，所经过的宝石总数（即这些段的长度之和）。如果总长度超过 $n$（说明已经覆盖了整条项链甚至更多），则设为无穷大 $oo$。

• 当 $k=0$：$jump[0][i] = len[i]$。
• 当 $k>0$：从 $i$ 走 $2^{k-1}$ 段后，会落在位置 $nxt = (i + jump[k-1][i] - 1) \bmod n + 1$ 处，作为下一段的起点。因此：
  
  $$jump[k][i]=\min (jump[k-1][i]+jump[k-1][nxt],oo)$$

这样我们就能在 $O(\log n)$ 的时间内计算出从任意起点出发能走的最大段数。

计算最大段数的函数 go(u) 如下：

• 初始化已覆盖宝石数 cnt = 0，段数 ans = 0，当前起点 u。
• 从大到小枚举 $k$（从 $\log$ 上界往下）：
  • 如果 cnt + jump[k][u] <= n，说明再加 $2^k$ 段仍然不会超出项链总长度，则可以跳过去：
    • cnt += jump[k][u]
    • ans += (1 << k)
    • 更新起点 u = (u + jump[k][u] - 1) % n + 1
• 最后返回段数 ans。

为什么限制 cnt + jump[k][u] <= n？因为整个环只有 $n$ 枚宝石，我们划分的所有段必须恰好覆盖这 $n$ 枚宝石，总长度不能超过 $n$。在上述贪心策略下，最终的覆盖总长度一定就是 $n$（因为整条项链包含所有种类，最后一定正好用完）。控制不超过 $n$ 实际上就是在模拟“走完整条项链”的过程。

最后，对每个 $i \in [1,n]$ 调用 go(i)，取最大值即为答案。

时间复杂度分析

• 滑动窗口预处理 $len[i]$：$O(n)$。
• 倍增预处理：状态数 $O(n \log n)$，转移 $O(1)$，总 $O(n \log n)$。
• 对每个起点求答案：$O(n \log n)$。

整体时间复杂度 $O(n \log n)$，空间复杂度 $O(n \log n)$。在 $n \le 10^5$ 时完全可以接受。

参考代码（C++）

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int L = 20;            // 2^19 > 2e5，足够覆盖 n
6const int N = 2e5 + 5;
7const int oo = 1e9;          // 无穷大，代表长度超过 n
8
9int n, m;
10int t[N];                    // 复制后的宝石数组，长度为 2n
11int jump[L][N];              // 倍增数组
12int cnt[N], tot;             // 滑动窗口用的计数数组和种类数
13int ans;
14
15// 计算从位置 u 开始最多能切多少段
16int go(int u) {
17    int cnt_len = 0, seg = 0;   // 已覆盖长度，已切段数
18    for (int i = L - 1; i >= 0; i--) {
19        if (cnt_len + jump[i][u] <= n) {
20            cnt_len += jump[i][u];
21            seg += 1 << i;
22            u = (u + jump[i][u] - 1) % n + 1; // 跳到下一段的起点
23        }
24    }
25    return seg;
26}
27
28int main() {
29    scanf("%d%d", &n, &m);
30    for (int i = 1; i <= n; i++) {
31        scanf("%d", &t[i]);
32        t[i + n] = t[i];          // 复制一遍，处理环
33    }
34
35    // 滑动窗口求最短合法段
36    for (int i = 1, r = 0; i <= n; i++) {
37        while (tot < m) {         // 未包含全部种类则右移 r
38            r++;
39            if (!cnt[t[r]]) tot++;
40            cnt[t[r]]++;
41        }
42        jump[0][i] = r - i + 1;   // 最短段长度
43        // 左端点 i 移出窗口
44        cnt[t[i]]--;
45        if (!cnt[t[i]]) tot--;
46    }
47
48    // 倍增预处理
49    for (int i = 1; i < L; i++) {
50        for (int j = 1; j <= n; j++) {
51            int nxt = (j + jump[i-1][j] - 1) % n + 1;
52            jump[i][j] = min(jump[i-1][j] + jump[i-1][nxt], oo);
53        }
54    }
55
56    // 枚举起点，取最大段数
57    for (int i = 1; i <= n; i++)
58        ans = max(ans, go(i));
59
60    printf("%d\n", ans);
61    return 0;
62}

代码细节说明

• 数组大小：宝石数组 t 开到 $2n$，而 jump 的第二维只需开到 $n$，因为只需要存储起点在 $1 \sim n$ 的信息。
• 无穷大常量 oo：取一个大于 $n$ 的数（如 $10^9$），在加法时防止溢出，并且在判断时只要超过 $n$ 就不会被选择。
• 滑动窗口：利用了 cnt 数组统计窗口内各宝石的出现次数，tot 记录当前不同种类数。当 tot == m 时窗口满足条件。
• 循环跳转：go() 函数贪心地尝试跳 $2^k$ 段，利用二进制拆分可以恰好用若干段拼出最大段数，同时保证不超出项链总长度 $n$。
• 取模细节：(u + len - 1) % n + 1 是为了将位置映射回 $1 \sim n$，实现环上移动。

总结

本题的关键在于两步转化：

1. 贪心地将每一段取到最短，把问题转化为求最短合法段和跳转；
2. 使用倍增优化跳转过程，使得枚举所有起点的复杂度降为 $O(n \log n)$。

这种“环上贪心划分 + 倍增”的方法在项链、环上覆盖等问题中非常常见，值得熟练掌握。