六、完善程序-2

缺陷生产线测试

工厂有n条生产线（编号0~n-1），已知恰有一条存在缺陷。每一轮测试为：从若干生产线的产品取样混合成一个批次发给客户，若批次含缺陷产品则退货（结果记为1），否则正常收货（结果记为0）。限制：所有批次中最多只能有k次退货（结果1的次数≤k）。目标：设计最少的测试轮数w，保证根据反馈结果唯一确定缺陷生产线。
程序包含三部分：①确定最小w；②生成最优测试方案；③根据测试结果推断缺陷生产线。程序确定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;
}


long long count_patterns(int w, int k) {
    long long total = 0;
    for (int t = 0; t <= min(w, k); ++t) {
        total += comb(w, t);  
    }
    return total;
}

int test_subset(const vector<vector<int>> &plan);

int solve(int n, int k) {
    
    int w = 1;
    while (①) {  
        ++w;
    }
    cout << w << endl;

    
    vector<vector<int>> code(n, vector<int>(w, 0));  
    int idx = 0;  
    vector<int> bits(w, 0);  
    for (int ones = 0; ones <= k && idx < n; ++ones) {  
        
        fill(bits.begin(), bits.end(), 0);
        fill(bits.begin(), bits.begin() + ones, 1);
        do {
            
            for (int b = 0; b < w; ++b) {
                code[idx][b] = bits[b];
            }
            idx++;
            if (idx >= n) break;  
        } while (std::②);  
    }

   
    vector<vector<int>> plan(w);
    for (int i = 0; i < w; ++i) { 
        for (int j = 0; j < n; ++j) {  
            if (③) {  
                plan[i].push_back(j);
            }
        }
    }

   
    int signature = test_subset(plan);

   
    vector<int> sig_bits(w, 0);
    for (int i = 0; i < w; ++i) {
        if (④) {  
            sig_bits[i] = 1;
        }
    }

    for (int j = 0; j < n; ++j) {
        if (⑤) {  
            return j;
        }
    }
    return -1;  
}

int main() {
    int n, k;
    cin >> n >> k;  
    int ans = solve(n, k);  
    cout << ans << endl;
    return 0;
}

信息学奥赛历年真题

Quiz Summary

Information

Results

Results

Categories

1. Question

2. Question

3. Question

4. Question

5. Question