CSP-S 提高级 · CSP 2025 提高级第一轮 第 20 题

工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有 $n$ 条生产线（编号 $0 \sim n-1$），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为 1），否则正常收货（记为 0）。受售后压力限制，在所有发货批次中，最多只能有 $k$ 次退货（即结果为 1 的次数 $\leq k$）。工厂的目标是，设计最少的间接测试轮数 $w$（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标，包含两部分：i) 确定 $w$ 的最小值，并设计最优测试方案；ii) 根据测试结果推断存在缺陷的生产线。该程序确定 $w$ 最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此 $w$ 轮测试的可能结果总数不应少于生产线数量。

test_subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第 1 批次、最高位是第 $w$ 批次）；其实现在此处未给出。

试补全程序。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;

long long comb(int w, int i) {
    if (i < 0 || i > w) {
        return 0;
    }
    long long res = 1;
    for (int t = 1; t <= i; ++t) {
        res = res * (w - t + 1) / t;
    }
    return res;
}

// 计算长度为 w、1 的个数 ≤ k 的码字总数
long long count_patterns(int w, int k) {
    long long 

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是带约束的组合枚举与群体测试编码。拿到题先想：w 轮测试能产生多少种‘退货次数≤k’的码字？只要这个数≥n，就够区分 n 条线了。于是核心就是写个函数把所有满足 1 的个数≤k 的二进制串数出来，再用它去判定 w 是否足够。

最容易栽的坑有两个：一是把总码字数当成 2^w，忘了题目限定了最多 k 次退货，必须用组合数求和 ΣC(w,i)；二是生成码字时初始化为全 1 后用 next_permutation，因为全 1 是字典序最小的排列，next_permutation 直接跳到最后，根本走不完所有组合，必须用 prev_permutation 从最大字典序往下遍历。

这道题考什么

这是一道结合组合数学与模拟的群体测试（Group Testing）问题。工厂要把 n 条生产线分成若干批次送检，每轮测试相当于检查一个二进制位：该生产线是否出现在这一轮里。如果某条生产线是缺陷的，那么所有包含它的批次都会退货（记为 1），否则正常（记为 0）。因此，缺陷生产线对应一个长度为 w 的二进制码字，码字中 1 的个数就是退货次数。

题目的硬性约束是：所有发货批次中，退货总次数不能超过 k。也就是说，我们只能使用那些“1 的个数 ≤ k”的码字。工厂的目标是找到最小的 w，使得这样的码字总数至少为 n，从而能一一对应地给每条生产线分配一个唯一的码字。

核心概念与命题视角

群体测试编码：每条生产线对应一个 w 位二进制串。若第 i 位为 1，表示该生产线被第 i 轮测试覆盖；为 0 则不覆盖。缺陷生产线产生的反馈签名就是它自己的码字。

约束下的码字计数：无约束时 w 位串共有 2^w 种，但本题限定了 1 的个数 ≤ k。因此总数是组合数之和：

\[\sum_{t=0}^{\min(w,k)} \binom{w}{t}\]

命题人喜欢在这里挖坑：很多学生看到“二进制串”就下意识写 (1<<w)，完全忽略了退货次数上限。题目给的辅助函数 count_patterns(w, k) 已经实现了这个求和，解题的关键就是理解它的作用并把它用在对 w 的判定上。

生成策略：要枚举所有满足条件的码字，最直接的方式是先把码字按“1 的个数”分组（0 个 1、1 个 1、…、k 个 1），每组内再用全排列生成。初始码字设为全 1（字典序最大），然后用 prev_permutation 一步步往下走，直到全 0 为止，这样就能遍历该组所有排列。

思考心法：拿到题先想什么

1. 确定 w 的最小值： - 思路：从小到大尝试 w = 1, 2, 3, …，每轮计算 count_patterns(w, k)。 - 判定条件：当这个计数值 ≥ n 时，当前的 w 就是答案。 - 代码实现：用一个 while 循环，循环条件就是“还能不够”，即 count_patterns(w, k) < n。

2. 生成测试方案： - 先统计需要多少轮：w 已求出。 - 然后按“1 的个数”从 0 到 k 依次生成码字，直到凑够 n 条为止。 - 对每个固定的 ones 数，构造一个初始全为 1 的数组，再用 prev_permutation 遍历所有排列。 - 每生成一个码字就填入 code 矩阵，同时统计已生成的数量，达到 n 就停止。

3. 构造发货计划： - plan[i] 表示第 i 轮测试包含哪些生产线。 - 遍历 code 矩阵，如果 code[j][i] == 1，说明第 j 条生产线参加了第 i 轮，就把 j 加进 plan[i]。

4. 执行测试并解码： - 调用 test_subset(plan) 得到签名 signature（一个整数，二进制位表示各轮结果）。 - 把 signature 拆成 w 个位存入 sig_bits。 - 最后遍历所有码字，找到与 sig_bits 完全相等的那一条，其下标就是缺陷生产线编号。

逐空推演（对应题目填空）

① 处：while 循环要一直执行到码字总数≥n 为止，所以条件必须是“还不够”，即 count_patterns(w, k) < n。选 B。

② 处：生成固定 ones 数的所有排列，初始为全 1（字典序最大），必须用 prev_permutation 才能一步步往下走。选 B。

③ 处：plan[i] 收集第 i 轮参与的生产线，即 code[j][i] == 1 的那些 j。选 D。

④ 处：提取签名的第 i 位，标准做法是 (signature >> i) & 1。选 A。

⑤ 处：匹配码字与签名，直接用 code[j] == sig_bits 即可。选 B。

避坑指南

• 坑 1：忘记退货限制。很多同学看到“二进制串”就写 (1<<w)，结果在 n 较大时 w 会远大于最优值，甚至超时。务必记住本题是“最多 k 次退货”，必须用组合数求和。
• 坑 2：排列方向搞反。全 1 是字典序最小，next_permutation 会直接跳到末尾，导致只生成一个码字就退出。必须用 prev_permutation 从最大往最小遍历。
• 坑 3：生成顺序。题目要求先按 ones 数从小到大生成（0 个 1、1 个 1、…），这样能保证码字按字典序自然排列，也符合出题人设计 code 矩阵时的预期。
• 坑 4：解码时位数搞错。签名是 w 位，但 sig_bits 要开成 w 个元素，循环下标从 0 到 w-1，别写成 w 到 2w-1 之类。

考频与趋势

从题库统计看，枚举/模拟类题目共 178 题，覆盖 2010-2026 年，近年热度明显上升：2026 年 38 题、2025 年 1 题、2024 年 1 题、2022 年 2 题等；排列组合基础共 147 题，2026 年 12 题、2025 年 43 题、2024 年 40 题，呈现逐年递增趋势；计数原理共 36 题，2025 年 5 题、2024 年 5 题、2023 年 3 题；群体测试作为组合编码的具体场景，在 CSP 提高级中已出现过 1 题（本题），属于较新的题型。

综合来看，这类“带约束的组合枚举 + 编码匹配”的题目在 CSP 提高级和 GESP 高级别中越来越常见，命题人倾向于把组合数求和、排列生成、矩阵构造、二进制位提取等多个知识点打包在一起，考察学生的综合建模能力。

预测

基于 2024-2026 年排列组合与模拟题目的爆发式增长，以及“群体测试”在 CSP 提高级中首次出现的事实，可以预测：未来两三年（2027-2029），CSP 提高级或 GESP 六级/七级极大概率会出现类似的“带约束编码/分组测试”题目，可能换一种约束（例如“1 的个数≥m”或“1 的个数在 [a,b] 区间”），或者把解码过程改成“找出所有可能的缺陷集合”。解题思路依然离不开组合数求和与 prev_permutation 的熟练运用。

若数据不足以支撑更具体的预测，则说明：暂无足够依据预测更细粒度的题型变化，但上述大方向是可靠的。

总结

本题的算法主线非常清晰： 1. 用 count_patterns 找到最小 w； 2. 按 ones 数从小到大，用 prev_permutation 生成所有合法码字； 3. 从码字矩阵构造发货计划； 4. 调用测试接口得到签名； 5. 把签名拆位，与码字矩阵逐行匹配，找到缺陷生产线。

只要抓住“退货次数≤k”这个约束，就不会掉进 (1<<w) 的坑；只要记住全 1 是字典序最小，就不会在排列生成上翻车。剩下的就是细心实现和调试。