「CEOI2024」核酸检测 题解

题目概述

这是一个自适应分组检测（Adaptive Group Testing）问题。已知 $N$ 个样本，每个样本独立的阳性概率为 $P$，可以通过混合检测判断样本子集中是否含有阳性样本。目标是用最少的期望检测次数确定所有样本的阳性状态。

算法思路

核心思想：动态规划 + 信息论贪心

该解法基于概率动态规划，预处理出最优的检测策略，然后在每个场景中根据实际检测结果动态调整检测方案。

关键定义

• $n$: 样本总数
• $p$: 单个样本阳性概率
• $pw[i]$: 前 $i$ 个样本全为阴性的概率，即 $(1-p)^i$
• $f[i][j]$: 在剩余 $i$ 个待检测样本，且已知其中恰好有 $j$ 个阳性的情况下，完成剩余检测的最小期望次数
• $path[i][j]$: 对应的最优决策（检测的样本数）

代码解析

1. 初始化与概率预处理

double p, pw[MX], f[MX][MX];
int n, path[MX][MX];
char ask[MX], ans[MX];

void init() {
    memset(ask, '0', sizeof(char) * n);
    double t;
    pw[0] = 1;

    // 计算前i个样本全为阴性的概率
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * (1 - p);
    }

这里 $pw[i] = (1-p)^i$ 表示检测 $i$ 个样本时全部为阴性的概率。

2. 动态规划求解最优策略

    for (int i = 1; i <= n; i++) {
        // 情况1：已知有1个阳性，逐个检测
        f[i][1] = f[i - 1][0];
        path[i][1] = 1;

        // 情况2：已知有j个阳性 (j >= 2)
        for (int j = 2; j <= i; j++) {
            f[i][j] = INF;
            
            // 枚举这次检测的样本数k
            for (int k = 1; k <= j; k++) {
                // 期望次数 = 1(本次检测) + 后续期望次数
                t = 1 + (1 - P(j, k)) * f[i][k] + P(j, k) * f[i - k][j - k];
                
                if (t < f[i][j]) {
                    f[i][j] = t;
                    path[i][j] = k;
                }
            }
        }

        // 情况3：阳性数量未知
        f[i][0] = INF;
        for (int j = 1; j <= i; j++) {
            t = 1 + pw[j] * f[i - j][0] + (1 - pw[j]) * f[i][j];
            
            if (t < f[i][0]) {
                f[i][0] = t;
                path[i][0] = j;
            }
        }
    }
}

状态转移解释：

• 已知阳性数 $j=1$：只能逐个检测，$f[i][1] = f[i-1][0]$
• 已知阳性数 $j \geq 2$：检测 $k$ 个样本，有两种可能：
  • 检测到阳性：剩余 $i-k$ 个样本中有 $j-k$ 个阳性
  • 未检测到阳性：剩余 $i$ 个样本中有 $k$ 个样本必含阳性
• 阳性数未知：检测 $j$ 个样本，有两种可能：
  • 全阴性：概率 $pw[j]$，剩余 $i-j$ 个样本状态未知
  • 有阳性：概率 $1-pw[j]$，确定 $i$ 个样本中有阳性

3. 辅助函数：条件概率计算

double P(int l, int k) {
    return (pw[k] - pw[l]) / (1 - pw[l]);
}

计算在已知 $l$ 个样本中至少有一个阳性的条件下，前 $k$ 个样本中包含阳性的概率。

4. 检测执行函数

bool query(int l, int r) {
    for (int i = l; i <= r; i++) {
        ask[i] = '1';
    }
    bool ret = test_students();
    for (int i = l; i <= r; i++) {
        ask[i] = '0';
    }
    return ret;
}

检测从 $l$ 到 $r$ 的样本区间。

5. 主检测逻辑

void find_positive() {
    memset(ans, '0', sizeof(char) * n);
    
    for (int i = 0, j = 0, t; i < n;) {
        t = n - i;  // 剩余样本数
        
        if (j == 1) {
            // 已知当前样本为阳性
            ans[i] = '1';
            i++;
            j = 0;
        } else {
            // 根据预计算策略进行检测
            bool fl = query(i, i + path[t][j] - 1);
            
            if (fl) {
                // 检测到阳性，更新已知信息
                j = path[t][j];
            } else {
                // 未检测到阳性，跳过已检测样本
                i += path[t][j];
                if (j) {
                    j -= path[t][j];
                }
            }
        }
    }
}

执行流程：

• $i$: 当前已确定的样本位置
• $j$: 已知的阳性数量
• 根据剩余样本数 $t$ 和已知阳性数 $j$，查询预计算的 $path$ 数组获得最优检测数量
• 根据检测结果更新状态

算法复杂度

• 预处理：$O(N^3)$，对于 $N=1000$ 可能较慢，但只需执行一次
• 每次检测：$O(N)$
• 空间复杂度：$O(N^2)$

优化点

1. 概率模型：利用已知的阳性概率 $P$ 优化检测策略
2. 自适应调整：根据实际检测结果动态调整后续检测方案
3. 期望最小化：通过动态规划求得期望检测次数最小的策略

适用场景

该算法在 $P$ 较小（如 $P < 0.2$）时效果显著，因为阳性样本稀少时，分组检测可以快速排除大量阴性样本。当 $P$ 较大时，可能直接逐个检测更优。