问题重述

我们有 $N$ 种颜色，每种颜色 $M$ 个团子，共 $NM$ 个团子。要用 $M$ 根竹签串出 $M$ 个「一流团子串」，每个串包含每种颜色恰好一个团子。

我们可以使用团子检测器：输入一些团子集合，返回用这些团子最多能制作多少个一流团子串。

目标：在最多使用 $50000$ 次检测的情况下，找出正确的分组方案。

---

关键限制分析

1. 查询次数限制

• 最多 $50000$ 次 Query
• $N \leq 400$, $M \leq 25$，所以 $NM \leq 10000$
• 平均每个团子只能查询约 $5$ 次

2. 问题结构

• 每组是一个完美匹配：包含每种颜色恰好一个团子
• 检测器返回的是最大匹配数

---

核心思路：二分分组

1. 基本观察

如果我们知道某个团子属于哪一组，问题就解决了。但直接检测单个团子无法得到信息。

关键想法：对每个团子，用二分法确定它属于哪一组。

2. 二分法框架

对于每个团子 $p$，我们想知道：$p$ 属于前 $k$ 组中的哪一组？

设当前考虑团子 $p$，已知它属于前 $r$ 组中的某一组：

1. 令 $mid = \lfloor (l + r) / 2 \rfloor$
2. 构造测试集合：
   • 包含前 $mid$ 组的所有团子（除了 $p$ 本身）
   • 加上团子 $p$
3. 查询检测器：
   • 如果返回值 = $mid$，说明 $p$ 不能放在前 $mid$ 组 ⇒ $p$ 在 $mid+1$ 到 $r$ 组
   • 如果返回值 = $mid+1$，说明 $p$ 可以放在前 $mid$ 组 ⇒ $p$ 在 $l$ 到 $mid$ 组

3. 具体实现

def determine_group(p, groups):
    # groups: 已确定的前几组团子
    l, r = 1, len(groups) + 1  # 可能属于新的一组
    while l < r:
        mid = (l + r) // 2
        # 构建测试集合：前mid组的所有团子 + p
        test_set = set()
        for i in range(mid):
            test_set.update(groups[i])
        test_set.add(p)
        
        if Query(test_set) == mid:
            l = mid + 1  # p不能放在前mid组
        else:
            r = mid      # p可以放在前mid组
    return l

---

算法流程

1. 初始化

• 创建 $M$ 个空组
• 所有团子都未分配

2. 逐个分配团子

• 随机选择一个未分配的团子 $p$
• 用二分法确定 $p$ 应该属于哪一组
• 将 $p$ 加入对应组

3. 维护约束

在分配过程中，始终保持：

• 每组内颜色不重复
• 每组大小不超过 $N$

---

查询次数分析

1. 最坏情况分析

• 每个团子需要 $O(\log M)$ 次查询
• 总团子数：$NM$
• 总查询次数：$O(NM \log M)$

代入最大值：

• $N = 400$, $M = 25$, $\log M \approx 4.64$
• $400 \times 25 \times 4.64 \approx 46400$
• 满足 $50000$ 的限制

2. 实际优化

• 当组快满时，二分范围可以缩小
• 可以优先分配容易确定的团子

---

实现细节

1. 数据结构

• 用数组或列表存储每个组的团子
• 用集合记录每个组已包含的颜色
• 用布尔数组标记团子是否已分配

2. 测试集合构建

构建测试集合时要注意：

• 排除正在测试的团子 $p$（如果它已在某组中）
• 确保集合中每种颜色最多 $M$ 个团子

3. 边界情况

• 第一个团子：直接放入第一组
• 组已满：创建新组
• 颜色冲突：确保同组内颜色不重复

---

正确性证明

1. 二分法的正确性

引理：如果团子 $p$ 可以放在前 $k$ 组中，那么它一定可以放在前 $k+1$ 组中。

因此，二分条件是单调的：

• 返回值 = $mid$ ⇒ $p$ 不能在 $\leq mid$ 的组
• 返回值 = $mid+1$ ⇒ $p$ 可以在 $\leq mid$ 的组

2. 最终结果的正确性

• 每个组包含 $N$ 个不同颜色的团子
• 所有团子都被分配
• 共 $M$ 个组

---

复杂度总结

• 时间复杂度：$O(NM \log M)$ 次查询
• 空间复杂度：$O(NM)$ 存储分组信息
• 查询次数：约 $46400$ 次，满足限制

---

总结

这道题的核心在于：

1. 问题转化：将分组问题转化为对每个团子的二分查找问题
2. 检测器使用：利用检测器的返回值作为二分判断条件
3. 单调性分析：发现"如果可以放在前k组，那么可以放在前k+1组"的单调性质
4. 复杂度控制：通过二分法将查询次数控制在限制范围内

这种「通过二分法利用黑盒函数」的思路在交互题中非常常见，是解决此类问题的经典方法。