题目分析

这是一个典型的交互式批量检测问题。我们需要在有限的查询次数内，利用已知信息推断出所有蘑菇的类型。

核心约束

• 已知信息：蘑菇 0 必定是 A 类
• 查询函数：use_machine(x) 返回排列中相邻不同类蘑菇的对数
• 限制条件：最多 20000 次查询，总蘑菇数不超过 100000

算法核心思想

1. 信息利用最大化

关键观察：**已知类型的蘑菇可以作为"检测工具"**来推断未知蘑菇的类型。

2. 批量检测策略

将查询视为一个信息通道，每次查询尽可能传递更多信息：

• 将已知蘑菇和未知蘑菇交替排列
• 一次查询可以同时检测多个未知蘑菇
• 通过差异数反推每个未知蘑菇的类型

3. 自适应选择

动态选择使用哪个已知集合进行检测：

• 优先使用规模较大的已知集合
• 保证每次查询都能检测尽可能多的未知蘑菇

算法步骤详解

第一阶段：基础建立

1. 从蘑菇 0 开始（已知为 A 类）
2. 逐个检测蘑菇 1、2，建立初始的已知集合
3. 目标：快速获得一定数量的 A 类和 B 类蘑菇

第二阶段：批量处理

对于剩余蘑菇，循环执行：

1. 集合选择：比较已知 A 类和 B 类集合的大小，选择较大的
2. 批量构建：构建查询序列 [已知₁, 未知₁, 已知₂, 未知₂, ...]
3. 查询执行：调用 use_machine 获取差异数
4. 结果解析：根据差异模式推断每个未知蘑菇的类型

第三阶段：结果统计

• 直接返回 A 类集合的大小
• 由于检测过程中实时维护集合，结果立即可得

关键技术点

1. 查询序列设计

交替排列的好处：

• 每个未知蘑菇都与一个已知蘑菇相邻
• 差异数直接反映类型是否相同
• 可以独立推断每个未知蘑菇的类型

2. 差异数解析

对于查询序列中的每个位置：

• 差异数增加 ⇨ 当前未知蘑菇与相邻已知蘑菇类型不同
• 差异数不变 ⇨ 当前未知蘑菇与相邻已知蘑菇类型相同

3. 效率优化

• 平衡选择：总是用较大的集合检测，最大化单次查询的信息量
• 批量处理：一次查询检测 k 个蘑菇，将查询次数从 O(n) 降至 O(n/k)
• 实时更新：检测出的蘑菇立即加入相应集合，扩大检测能力

复杂度分析

令 k 为平均每次查询检测的蘑菇数：

• 查询次数：≈ n/k
• 总蘑菇数：≈ 2n（每个蘑菇在查询中出现约 2 次）
• 实际性能：在题目约束内轻松通过

思维启示

1. 信息论思维：将每次查询视为信息传输，最大化信息熵
2. 增量学习：利用已获得的信息来获取新信息
3. 资源平衡：在查询次数和查询规模间找到最优平衡点

这种"用已知探测未知"的思路在众多交互题中都有应用，是解决此类问题的经典范式。