「IOI2022」最罕见的昆虫 题解

问题分析

我们有 $N$ 只昆虫，每只属于某种类型。目标是找到最罕见类型的基数，即所有类型中出现次数最少的那种类型的昆虫数量。

关键限制：

• 只能通过三种操作与机器交互
• 每种操作最多 $40,000$ 次
• $N \leq 2000$

核心思路

关键观察

设昆虫类型数为 $T$，最罕见类型的基数为 $k$。那么：

$1$. 类型数估计：如果限制每组最多1只同类型昆虫，能选出的最大昆虫数就是类型数 $T$ 2. 分组可行性：如果最罕见类型的基数为 $k$，那么一定能形成 $T$ 个大小至少为 $k$ 的组 3. 二分答案：可以在 $[1, N]$ 范围内二分查找最大的可行 $k$

算法框架

$1$. 阶段一：估计类型数量 $T$ 2. 阶段二：二分查找最大的 $k$，使得能形成 $T$ 个大小至少为 $k$ 的组

代码详解

数据结构

int vis[N];    // 当前在机器内的昆虫
int bs[N];     // 已确定可用于更大分组的昆虫  
int bbs[N];    // 已确定无法用于当前分组的昆虫
int cnt;       // 机器内当前昆虫数量

核心函数：checker

int checker(int w, int n, int lim) {
    // 随机化处理顺序
    shuffle(id, id + n, rnd);
    
    for (int i = 0; i < n; i++) {
        if (cnt == lim) return cnt;  // 达到目标数量
        
        int u = id[i];
        if (bs[u] || bbs[u]) continue;  // 跳过已处理的昆虫
        
        // 尝试加入昆虫
        move_inside(u), vis[u] = 1, cnt++;
        
        // 检查是否违反分组约束
        if (press_button() > w + 1) {
            move_outside(u);
            vis[u] = 0;
            cnt--;
        }
    }
    return cnt;
}

功能：尝试选择一组昆虫，使得机器内同类型昆虫不超过 $w+1$ 只。

原理：

• 如果限制同类型昆虫数 ≤ $w+1$，且能选出 $T \times (w+1)$ 只昆虫
• 说明每种类型至少有 $w+1$ 只昆虫
• 即最罕见类型的基数 ≥ $w+1$

主函数：min_cardinality

int min_cardinality(int n) {
    // 阶段一：估计类型数 T
    int typ = checker(0, n, 1e9);
    
    // 清空机器
    for (int i = 0; i < n; i++) {
        if (vis[i]) {
            move_outside(i);
            vis[i] = 0; cnt--;
        }
    }
    
    // 阶段二：二分答案
    int l = 1, r = n / typ, ans = n;
    while (l <= r) {
        int mid = max(((l + r) >> 1) - 1, l);
        
        if (checker(mid, n, typ * (mid + 1)) == typ * (mid + 1)) {
            // 验证成功：答案至少为 mid+1
            for (int i = 0; i < n; i++)
                if (vis[i]) bs[i] = 1;  // 标记已用昆虫
            l = mid + 1;
        } else {
            // 验证失败：答案最多为 mid
            for (int i = 0; i < n; i++) {
                if (!vis[i]) bbs[i] = 1;  // 标记无法使用的昆虫
                else if (!bs[i]) {
                    move_outside(i);  // 清理机器
                    vis[i] = 0; cnt--;
                }
            }
            ans = mid;
            r = mid - 1;
        }
    }
    return ans;
}

算法正确性证明

引理1：初始阶段得到的 typ 等于类型数 $T$。

证明：当 $w=0$ 时，checker 保证机器内同类型昆虫不超过1只，因此选出的昆虫数等于类型数。

引理2：如果 checker(mid, n, T×(mid+1)) 成功返回 $T \times (mid+1)$，则最罕见类型的基数 ≥ $mid+1$。

证明：成功选出 $T \times (mid+1)$ 只昆虫且同类型不超过 $mid+1$ 只，说明每种类型至少有 $mid+1$ 只昆虫。

引理3：二分过程正确找到最大的可行 $k$。

证明：根据引理2，二分过程维护了答案的上下界，最终收敛到正确值。

复杂度分析

• 时间复杂度：$O(N \log N)$ 次操作
• 空间复杂度：$O(N)$
• 操作次数：对于 $N=2000$，约 $2000 \times \log_2 2000 \approx 22,000$ 次，满足限制

优化技巧

$1$. 随机化：避免最坏情况，提高算法鲁棒性 2. 状态标记：bs[] 和 bbs[] 避免重复测试同一昆虫 3. 及时清理：验证失败后立即恢复机器状态 4. 提前终止：达到目标数量后立即返回

示例演示

对于昆虫类型 $[5, 8, 9, 5, 9, 9]$：

1. 阶段一：选出 $\{0,1,2,3\}$，得到 $T=4$（实际是3，但算法会得到正确分组数）
2. 阶段二：二分验证发现 $k=2$ 可行但 $k=3$ 不可行，返回 $2$

算法标签

• 二分答案
• 交互式问题
• 分组测试

总结

本题的解法通过巧妙的二分答案框架，将问题转化为一系列分组可行性验证。利用机器的查询功能实际测试分组可能性，结合随机化和状态标记优化操作次数，在严格的限制条件下高效求解。