谁说完善程序一定要看题目描述的

__Cby___ · 2025-09-20 20:09:20 · 休闲·娱乐

本文章将讲解如何在不看题目描述的情况下做出完善程序 2（作者太菜了没看懂题目解法的中文描述）。
以下是题目：

01 #include <algorithm>
02 #include <cstddef>
03 #include <iostream>
04 #include <vector>
05 using namespace std;
06
07 long long comb(int w, int i) {
08     if (i < 0 || i > w) {
09         return 0;
10     }
11     long long res = 1;
12     for (int t = 1; t <= i; ++t) {
13         res = res * (w - t + 1) / t;
14     }
15     return res;
16 }
17
18 // 计算长度为 w、1 的个数 ≤ k 的码字总数
19 long long count_patterns(int w, int k) {
20     long long total = 0;
21     for (int t = 0; t <= min(w, k); ++t) {
22         total += comb(w, t);
23     }
24     return total;
25 }
26
27 // 抽象测试接口
28 int test_subset(const vector<vector<int>> &plan);
29
30 int solve(int n, int k) {
31     // === 第 1 步：求最小 w ===
32     int w = 1;
33     while (___①___) {
34         ++w;
35     }
36     cout << w << endl;
37
38     // === 第 2 步：生成测试方案 ===
39     vector<vector<int>> code(n, vector<int>(w, 0));
40     int idx = 0;
41     for (int ones = 0; ones <= k && idx < n; ++ones) {
42         vector<int> bits(w, 0);
43         fill(bits.begin(), bits.begin() + ones, 1);
44         do {
45             for (int b = 0; b < w; ++b) {
46                 code[idx][b] = bits[b];
47             }
48             ++idx;
49             if (idx >= n) {
50                 break;
51             }
52         } while (std::___②___);
53     }
54
55     vector<vector<int>> plan(w);
56     for (int i = 0; i < w; ++i) {
57         for (int j = 0; j < n; ++j) {
58             if (___③___) {
59                 plan[i].push_back(j);
60             }
61         }
62     }
63
64     // === 第 3 步：调用测试接口 ===
65     int signature = test_subset(plan);
66
67     // === 第 4 步：结果解码 ===
68     vector<int> sig_bits(w, 0);
69     for (int i = 0; i < w; ++i) {
70         if (___④___) {
71             sig_bits[i] = 1;
72         }
73     }
74
75     for (int j = 0; j < n; ++j) {
76         if (___⑤___) return j;
77     }
78 }
79
80 int main() {
81     int n,k;
82     cin >> n >> k;
83     int ans = solve();
84     cout << ans << endl;
85     return 0;
86 }

38. ①处应填（ ）
A. (1 << w) < n
B. count_patterns(w,k) < n
C. count_patterns(k,w) < n
D. comb(w,k) < n
解析：注意到他定义了 count_patterns 且后面都没调用，所以我们认为这里要用 count_patterns。根据 count_patterns 的定义：
long long count_patterns(int w, int k)
可知选 B。

39. ②处应填（ ）
A. next_permutation(bits.begin(), bits.end())
B. prev_permutation(bits.begin(), bits.end())
C. next_permutation(bits.begin(), bits.begin()+ones)
D. prev_permutation(bits.begin(), bits.begin()+ones)
解析：发现 bits 的 bits.begin() 到 bits.begin() + ones 都是 1，所以 C，D 实际上没有任何效果，排除。bits 由一段全为 1 的前缀和一段全为 0 的后缀构成， next_permutation() 会使字典序增大，这里 bits 字典序已经最大了，所以排除 A，C。
可知选 B。

40. ③处应填（ ）
A. (j >> i) & 1
B. (i >> j) & 1
C. code[i][j] == 1
D. code[j][i] == 1
解析：联系 45 行至 47 行：

45             for (int b = 0; b < w; ++b) {
46                 code[idx][b] = bits[b];
47             }

code 的第二维应当是 0 到 w-1。回到题目：

56     for (int i = 0; i < w; ++i) {
57         for (int j = 0; j < n; ++j) {
58             if (___③___) {
59                 plan[i].push_back(j);
60             }
61         }
62     }