题目概述

有 $k$ 个相同的礼物盒，每个盒子中有 $n$ 个礼物，类型序列为 $a_1, a_2, \ldots, a_n$（从上到下）。礼物按以下顺序分发：

• 先发第一个盒子的顶部到底部
• 然后第二个盒子，依此类推
• 每个参赛者可以收到多个礼物，但类型数不能超过 $t$

要求：找到最少需要多少参赛者才能发完所有礼物。

---

问题分析

关键观察

1. 分发顺序：礼物按 $(a_1, a_2, \ldots, a_n)$ 重复 $k$ 次
2. 类型限制：每个参赛者最多 $t$ 种不同类型
3. 目标：最小化参赛者数量

问题转化

这相当于在一个循环序列中，找到最小的分割次数，使得每个段内不同元素个数 ≤ $t$。

---

算法思路

核心思想：滑动窗口 + 周期检测

步骤1：预处理

• 将礼物类型映射到 0~c-1（c 为不同类型数）
• 如果 c ≤ t，直接输出 1（一个人就能拿完）

步骤2：计算每个起点的下一个分割点

对于每个起始位置 $i$，用滑动窗口找到最小的 $l$，使得 $[i, l]$ 区间内不同类型数 > $t$，则分割点为 $l$。

map<int, int> s;  // 记录当前窗口内各类型出现次数
for (int i = 0, l = 0; i < n; i++) {
    while (true) {
        s[a[l % n]]++;  // 扩展右边界
        if (s.size() > t) {  // 超过类型限制
            nx[i] = l;  // 记录分割点
            s.erase(a[l % n]);  // 移除导致超限的类型
            if (l < n) g[l].emplace_back(i);  // 构建依赖图
            break;
        }
        l++;
    }
    // 移动左边界
    if (!--s[a[i]]) s.erase(a[i]);
}

步骤3：计算跳转距离

通过 BFS 计算从每个位置跳转到下一个周期需要经过多少分割点：

queue<int> q;
for (int i = n-1; i >= 0; i--) 
    if (nx[i] >= n)  // 跨越周期边界
        q.emplace(f[i] = i);  // 记录终点

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i : g[u])  // 处理依赖关系
        f[i] = f[u], d[i] = d[u] + 1, q.emplace(i);
}

这里：

• f[i]：从位置 $i$ 开始跳转的终点
• d[i]：从 $i$ 到终点需要经过的分割点数

步骤4：模拟分发过程

利用周期性质加速计算：

vector<int> w(n << 1), b(n, -1);
for (int i = c = 0, p = 0; i < k; i++) {
    if (~b[p]) {  // 发现周期
        int x = (k - b[p]) / (i - b[p]);  // 完整周期数
        int r = (k - b[p]) % (i - b[p]);  // 剩余迭代次数
        c += (c - w[b[p]] + d[p]) * (x - 1);  // 计算周期贡献
        
        for (int j = 0; j < r; j++)  // 处理剩余部分
            c += d[p], p = nx[f[p]] - n;
        break;
    }
    // 记录状态
    w[b[p] = i] = (c += d[p]), p = nx[f[p]] - n;
}
cout << c + k << endl;  // 总分割点数 + 周期数

---

算法详解

为什么这样计算？

• 总参赛者数 = 总分割点数 + 1
• 每跨越一个分割点，就需要一个新的参赛者
• 由于序列周期性，分割模式也会周期性重复

关键变量含义

• nx[i]：从位置 $i$ 开始，第一个使得类型数超过 $t$ 的位置
• d[i]：从 $i$ 到下一个周期开始需要的新参赛者数
• f[i]：从 $i$ 开始跳转的终点位置
• b[p]：记录位置 $p$ 第一次出现的时间
• w[i]：记录第 $i$ 次迭代时的累计分割点数

---

样例解析

样例1

输入：2 4 1
      1 2
输出：8

序列：(1,2) 重复4次 → 1,2,1,2,1,2,1,2

由于 t=1，每个参赛者只能拿一种类型：

• 参赛者1：1 (类型1)
• 参赛者2：2 (类型2)
• 参赛者3：1 (类型1)
• 参赛者4：2 (类型2)
• ...共需要8个参赛者

样例2

输入：4 3 1  
      1 1 2 1
输出：7

序列：(1,1,2,1) 重复3次

由于 t=1，分割点很多，需要7个参赛者。

样例3

输入：7 2 3
      1 2 3 4 5 6 7  
输出：5

序列有7种不同类型，t=3，可以更有效地分组。

---

复杂度分析

• 预处理：$O(n)$（每个元素进出map一次）
• BFS：$O(n)$
• 周期检测：$O(n)$
• 总复杂度：$O(n)$

对于 $n \leq 300,000$ 可以接受。

---

算法亮点

1. 滑动窗口：高效计算每个起点的分割位置
2. 周期检测：利用序列重复性加速计算
3. 依赖图：通过图结构传播跳转信息
4. 状态记录：检测并利用周期性避免重复计算

---

总结

这道题的核心在于将礼物分发问题转化为循环序列分割问题：

1. 问题转化：将礼物序列视为循环序列，找最优分割
2. 滑动窗口：确定每个位置的最远可达点
3. 周期利用：由于盒子相同，分割模式周期性重复
4. 加速计算：检测周期后直接计算，避免模拟每个盒子

这种"滑动窗口 + 周期检测"的方法在处理循环序列问题时非常有效，特别是在序列很长但具有重复模式的情况下。