单项选择

T1

有 \(5\) 个红色球和 \(5\) 个蓝色球，它们除了颜色之外完全相同。将这 \(10\) 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

  • A. 25
  • B. 30
  • C. 6
  • D. 120
答案

C

将 \(5\) 个红色球排成一排，共有 \(6\) 个空隙（_R_R_R_R_R_）。

将 \(5\) 个蓝色球，放在 \(6\) 个空中，共 \(\binom{6}{5} = 6\)

T2

在 KMP 算法中，对于模式串 \(P = \text{abacaba}\)，其 next 数组（ \(next[i]\) 定义为模式串 \(P[0\dots i]\) 最长公共前后缀的长度，且数组下标从 \(0\) 开始）的值是什么？

  • A. {0,0,1,0,1,2,3}
  • B. {0,1,2,3,4,5,6}
  • C. {0,0,1,1,2,2,3}
  • D. {0,0,0,0,1,2,3}
答案

A

模拟即可。

T3

对一个大小为 \(16\)（下标 \(0 \sim 15\)）的数组上构建满线段树。查询区间 \([3,11]\) 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？

  • A. 7
  • B. 8
  • C. 9
  • D. 10
答案

B

T4

将字符串 cat, car, cart, case, dog, do 插入一个空的 Trie 树（前缀树）中。构建完成的 Trie 树（包括根结点）共有多少个结点？

  • A. 8
  • B. 9
  • C. 10
  • D. 11
答案

D

T5

对于一个包含 \(n\) 个顶点和 \(m\) 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

  • A. 只有 \(1\) 种
  • B. 最多 \(n\) 种
  • C. 等于 \(n-m\) 种
  • D. 以上都不对
答案

D

拓扑排序的数量取决于图的具体结构，没有一个简单的公式可以计算。

如，没有边为 \(n!\) 种，是链则只有 \(1\) 种。

T6

在一个大小为 \(13\) 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 \(H(key)=key \mod 13\)。依次插入关键字 18, 26, 35, 9, 68, 74。插入 74 后，它最终被放置在哪个索引位置？

  • A. 5
  • B. 7
  • C. 9
  • D. 11
答案

D

  1. \(18 \mod 13 = 5\)
  2. \(26 \mod 13 = 0\)
  3. \(35 \mod 13 = 9\)
  4. \(9 \mod 13 = 9\)，\(9\) 冲突，放在第 \(10\) 个位置
  5. \(68 \mod 13 = 3\)
  6. \(74 \mod 13 = 9\)，\(9,10\) 冲突，放在第 \(11\) 个位置

T7

一个包含 \(8\) 个顶点的完全图（顶点的编号为 \(1\) 到 \(8\)），任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点 \(3\) 和 \(7\) 之间的边权重为 \(|7 − 3| = 4\)。该图的最小生成树的总权重是多少？

  • A. 7
  • B. 8
  • C. 9
  • D. 10
答案

A

用 Kruskal 算法求解：

边权最小分别为 \(1\rightarrow 2=1,2\rightarrow3=1,3\rightarrow4=1,4\rightarrow5=1,5\rightarrow6=1,6\rightarrow7=1\)。

总权重为 \(7\)。

T8

如果一棵二叉搜索树的后序遍历序列是 2, 5, 4, 8, 12, 10, 6，那么该树的前序遍历序列是什么？

  • A. 6, 4, 2, 5, 10, 8, 12
  • B. 6, 4, 5, 2, 10, 12, 8
  • C. 2, 4, 5, 6, 8, 10, 12
  • D. 12, 8, 10, 5, 2, 4, 6
答案

A

后序遍历 2, 5, 4, 8, 12, 10, 6，根是最后一个元素 \(6\)。

二叉搜索树保证：左子树 < 根 < 右子树，所以左子树节点 2, 5, 4，右子树 8, 12, 10。

再结合后序遍历，可得：

即，前序遍历 6, 4, 2, 5, 10, 8, 12。

T9

一个 0-1 背包问题，背包容量为 \(20\)。现有 \(5\) 个物品，其重量和价值分别为 7，5，4，3，6 和 15，12，9，7，13。装入背包的物品能获得的最大总价值是多少？

  • A. 43
  • B. 41
  • C. 45
  • D. 44
答案

D

发现重量小的，价值也小，可以直接枚举。

  1. 2, 3, 4, 5，价值 \(41\)。
  2. 1, 2, 3, 4，价值 \(43\)。
  3. 1, 3, 4, 5，价值 \(44\)。

T10

在一棵以结点 \(1\) 为根的树中，结点 \(12\) 和结点 \(18\) 的最近公共祖先 (LCA) 是结点 \(4\)。那么下列哪个结点的 LCA 组合是不可能出现的？

  • A. LCA(12, 4) = 4
  • B. LCA(18, 4) = 4
  • C. LCA(12, 18, 4) = 4
  • D. LCA(12, 1) = 4
答案

D

\(1\) 是根节点，\(1\) 与任何节点的 LCA 都是 \(1\)。

T11

递归关系式 \(T(n) = 2T(\frac{n}{2}) + O(n^2)\) 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

  • A. \(O(n)\)
  • B. \(O(n\log n)\)
  • C. \(O(n^2)\)
  • D. \(O(n^2 \log n)\)
答案

C

主定理： \(\log_b a = \log_2 2 = 1\)，\(2 > 1\)，因此为 \(O(n^2)\)。

T12

在一个初始为空的最小堆（min-heap）中，依次插入元素 20, 12, 15, 8, 10, 5。然后连续执行两次“删除最小值”（delete-min）操作。请问此时堆顶元素是什么？

  • A. 10
  • B. 12
  • C. 15
  • D. 20
答案

A

即第三小的值。

T13

\(1\) 到 \(1000\) 之间，不能被 \(2\)、\(3\)、\(5\) 中任意一个数整除的整数有多少个？

  • A. 266
  • B. 267
  • C. 333
  • D. 734
答案

A

容斥原理。

  1. 能被 \(2,3,5\) 整除的数：
    • \(2\)：\(\lfloor 1000/2 \rfloor = 500\)
    • \(3\)：\(\lfloor 1000/3 \rfloor = 333\)
    • \(5\)：\(\lfloor 1000/5 \rfloor = 200\)
  2. 能被两两相乘整除的数：
    • \(2\times 3 = 6\): \(\lfloor 1000/6 \rfloor = 166\)
    • \(2\times 5 = 10\): \(\lfloor 1000/10 \rfloor = 100\)
    • \(3\times 5 = 15\): \(\lfloor 1000/15 \rfloor = 66\)
  3. 能被 \(3\) 个数整除的数：
    • \(2\times 3\times 5 = 30\): \(\lfloor 1000/30 \rfloor = 33\)

总答案即为 \(1000 - (500+333+200 - 166-100-66+33) = 266\)。

T14

斐波那契数列的定义为 \(F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)\)。使用朴素递归方法计算 \(F(n)\) 的时间复杂度是指数级的。而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？

  • A. 递归函数调用栈开销过大
  • B. 操作系统对递归深度有限制
  • C. 朴素递归中存在大量的重叠子问题未被重复利用
  • D. 动态规划使用了更少的数据存储空间
答案

C

显然，朴素递归中存在大量的重叠子问题未被重复利用，这也是动态规划的优势所在。

T15

有 \(5\) 个独立的、不可抢占的任务 A1, A2, A3, A4, A5 需要在一台机器上执行（从时间 \(0\) 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 3, 4, 2, 5, 1 和 5, 10, 3, 15, 11。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

  • A. 处理时间最短的任务 A5
  • B. 截止时间最早的任务 A3
  • C. 处理时间最长的任务 A4
  • D. 任意一个任务都可以
答案

B

贪心模拟即可。

程序阅读

T16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
		++ans;
		return;
	}
	for (int i = 1; i <= n; ++i) {
		if (flag[i]) continue;
		if (k > 1 && i == p[k - 1] + 1) continue;
		p[k] = i;
		flag[i] = true;
		dfs(k + 1);
		flag[i] = false;
	}
	return;
}
int main() {
	scanf("%d", &n);
	dfs(1);
	printf("%d\n", ans);
	return 0;
}

判断题

  1. 当输入的 \(n=3\) 的时候，程序输出的答案为 \(3\)。
  2. 在 dfs 函数运行过程中，\(k\) 的取值会满足 \(1 \le k \le n+1\)。
  3. 删除第 \(19\) 行的 flag[i]=false;，对答案不会产生影响。

选择题

  1. 当输入的 \(n=4\) 的时候, 程序输出的答案为？
    • A. 11
    • B. 12
    • C. 24
    • D. 9
  2. 如果因为某些问题，导致程序运行第 \(25\) 行的 dfs 函数之前，数组 p 的初值并不全为 \(0\)，则对程序的影响是？
    • A. 输出的答案比原答案要小
    • B. 无法确定输出的答案
    • C. 程序可能陷入死循环
    • D. 没有影响
  3. 假如删去第 \(14\) 行的 if(flag[i]) continue;，输入 \(3\)，得到的输出答案是？
    • A. 27
    • B. 3
    • C. 16
    • D. 12
解析

程序为求解 \(p_i +1 \neq p_{i+1}\) 的长度为 \(n\) 的 排列 \(p\) 的方案数。

答案

TTFADC

判断题

  1. 手动模拟，得出答案为 \(3\)。
  2. 显然，第 \(25\) 行，\(k\) 初值为 \(1\)；第 \(9 \sim 12\) 行，\(k = n+1\) 就会返回。
  3. 显然，未清空标记，方案数会减少。

选择题

  1. 手动模拟。
  2. 不会影响，因为在计算 \(p_i\) 时，\(p_{i-1}\) 一定 被重新赋值完。
  3. 删去，则去掉了 排列 的限制，还是手动模拟。

T17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
    printf("now check:%d\n", h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are Right using %d checks\n", cnt_check);
        return true;
    } else {
        printf("Wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w = 0;
    for (w = 1; w * (w + 1) / 2 < n; ++w)
        ;
    for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
        if (check(nh)) {
            for (int j = nh - ti + 1; j < nh; ++j) {
                if (check(j)) {
                    assert_ans(j);
                    return;
                }
            }
            assert_ans(nh);
            return;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    int t;
    scanf("%d", &t);
    if (t == 1) {
        guess1(n);
    } else {
        guess2(n);
    }
    return 0;
}

注意：下述的 “猜测数” 为调用 check 函数的次数（即 cnt_check 的值）；“猜测正确” 的含义为 assert_ans 函数 return true（执行第 \(25\) 行所在分支）的情况；所有输入保证 \(1 \le k \le n\)。

判断题

  1. 当输入为 6 5 1 时，猜测次数为 \(5\)；当输入为 6 5 2 时，猜测次数为 \(3\)。
  2. 不管输入的 \(n\) 和 \(k\) 具体为多少，\(t=2\) 时的猜测数总是小于等于 \(t=1\) 时的猜测数。
  3. 不管 \(t=1\) 或 \(t=2\)，程序都一定会猜到正确结果。

选择题

  1. 函数 guess1 在运行过程中，cnt_broken 的值最多为？
    • A. 0
    • B. 1
    • C. 2
    • D. n
  2. 函数 guess2 在运行过程中，最多使用的猜测次数的量级为？
    • A. \(O(n)\)
    • B. \(O(n^2)\)
    • C. \(O(\sqrt{n})\)
    • D. \(O(\log n)\)
  3. 当输入的 \(n=100\) 时，代码中 \(t=1\) 和 \(t=2\) 分别需要的猜测次数最多分别为？
    • A. 100,14
    • B. 100,13
    • C. 99,14
    • D. 99,13
解析

今年最奇怪的题目

由 egg，cnt_broken 可以得出（？），我们假设这样一个情景：

现在你有两个一样的鸡蛋，你可以进行一种操作：

  • 把鸡蛋从一个高度 \(h\) 扔下来，观察它有没有摔碎。如果鸡蛋碎了，这个鸡蛋就不能再用了，你需要用另一个鸡蛋继续尝试，如果两个都碎了（You have no egg!），则游戏结束。

现在，你想知道会让鸡蛋摔碎的最小高度（guess1），和知道前者的最小操作次数（guess2）。

guess1

guess1 函数比较好懂，就是枚举所有可能的高度，这样会一定会摔碎 \(1\) 个鸡蛋。

guess2

guess2 函数略复杂，它将高度分为了几个区间，我们以 \(n = 15\) 为例，化为了 \([1,5],[6,9],[10,12],[13,14],[15,15]\) 五段，它们的长度依次递减，分别为 \(5,4,3,2,1\)。

对于每段区间，我们先尝试它的右端点，如果没摔碎说明高度足够，就尝试下一个区间。

如果摔碎了，因为只剩一个鸡蛋，只能模仿 guess1 从小到大依次尝试，求出最终答案。

这样摔碎鸡蛋的数量一定是 \(1\) 或 \(2\)。

答案

TFTBCA

判断题

  1. 手动模拟，得出答案为 \(5\)。
  2. 不一定，如果鸡蛋在很低的高度就碎了，guess2 需要额外尝试区间的右端点，多一次猜测。
  3. 显然正确。

选择题

  1. 显然为 \(1\)。
  2. 猜测次数的最大值 \(m\)，要满足 \(\frac{m(m-1)}{2} \ge n\)，解二次不等式得 \(m\) 的最小值为 \(\left\lceil\frac{1+\sqrt{1+8n}}{2}\right\rceil\)，量级估算为 \(\sqrt{2n} \approx \sqrt{n}\)。
  3. 手动模拟。

T18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
   int ans = 1;
    for (; k; k = k >> 1, x = x * x) {
        if (k & 1)
            ans = ans * x;
    }
    return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
    std::sort(ans1.begin(), ans1.end());
    int newcnt1 = 1;
    cntans1.push_back(1);
    for (int i = 1; i < cnt1; ++i) {
        if (ans1[i] == ans1[newcnt1 - 1]) {
            ++cntans1[newcnt1 - 1];
        } else {
            ans1[newcnt1++] = ans1[i];
            cntans1.push_back(1);
        }
    }
    cnt1 = newcnt1;
    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i = cnt2 - 1; i >= 0; --i) {
        for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
            ;
        if (las < cnt1 && ans1[las] + ans2[i] == 0)
            ans += cntans1[las];
    }
    printf("%lld\n", ans);
    return 0;
}

判断题

  1. 删除第 \(51\) 行的 std::sort(ans2.begin(), ans2.end()); 后，代码输出的结果不会受到影响。
  2. 假设计算过程中不发生溢出，函数 mpow(x, k) 的功能是求出 \(x^k\)。
  3. 代码中第 \(39\) 行到第 \(50\) 行的目的是为了将 ans1 数组进行“去重”操作。

选择题

  1. 当输入为 3 15 1 2 -1 2 1 2 时，输出结果为？
    • A. 4
    • B. 8
    • C. 0
    • D. 10
  2. 记程序结束前 p 数组元素的最大值为 \(P\)，则该代码的时间复杂度是？
    • A. \(O(n)\)
    • B. \(O(m^n \log m^n)\)
    • C. \(O(m^\frac{n}{2} \log m^\frac{n}{2})\)
    • D. \(O(m^\frac{n}{2} (\log m^\frac{n}{2} + \log P))\)
  3. 本题所求出的是？
    • A. 满足 \(a,b,c \in [1,m]\) 的整数方程 \(a^3+b^3=c^3\) 的解的数量
    • B. 满足 \(a,b,c \in [1,m]\) 的整数方程 \(a^2+b^2=c^2\) 的解的数量
    • C. 满足 \(x_i \in [0,m]\) 的整数方程 \(\sum_{i=1}^n k_i \cdot x_i^{p_i} = 0\) 的解的数量
    • D. 满足 \(x_i \in [1,m]\) 的整数方程 \(\sum_{i=1}^n k_i \cdot x_i^{p_i} = 0\) 的解的数量
解析

先看选择题第三问，首先排除 A,B 选项，根本没有出现输入的量。

观察第 \(24\) 行，枚举从 \(1\) 开始，故程序含义为：

  • 满足 \(x_i \in [1,m]\) 的整数方程 \(\sum_{i=1}^n k_i \cdot x_i^{p_i} = 0\) 的解的数量。
答案

FTTBDD

判断题

  1. \(52\) 到 \(59\) 行是双指针计算答案，不排序显然会影响结果。
  2. 快速幂。
  3. 显然。

选择题

  1. 结合程序意义，即求 \(x_1^2+x_3^2=x_2^2，x_i \in [1,15]\) 的方案数，可以手动枚举计算，也容易联想到就是求边长在 \(15\) 以内的直角三角形的数量。

完善程序

T19 特殊最短路

给定一个含 \(N\) 个点、\(M\) 条边的带权无向图，边权非负。起点为 \(S\)，终点为 \(T\)。对于一条 \(S\) 到 \(T\) 的路径，可以在整条路径中，至多选择一条边作为“免费边”：当第一次经过这条被选中的边时，费用视为 \(0\)；如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 \(S\) 到 \(T\) 的最小总费用。

以下代码求解了上述问题。试补全程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const long long INF = 1e18;

struct Edge {
	int to;
	int weight;
};
 
struct State {
	long long dist;
	int u;
	int used_freebie;//0 for not used, 1 for used
	bool operator>(const State &other) const {
		return dist > other.dist;
	}
};

int main() {
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	
	vector<vector<Edge>> adj(n + 1);
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
	priority_queue<State, vector<State>, greater<State>> pq;
	
	d[s][0]= 0;
	pq.push({0, s,   ①  });

	while(!pq.empty()) {
		State current =pq.top();
		pq.pop();
		
		long long dist = current.dist;
		int u= current.u;
		int used = current.used_freebie;
		
		if(dist >   ②  ){
			continue;
		}
		
		for (const auto &edge : adj[u]) {
			int v = edge.to;
			int w = edge.weight;
			
			if(d[u][used] + w <   ③  ){
				   ③  = d[u][used] + w;
				pq.push({  ③  , v , used});
			}
		
			if(used == 0){
				if(  ④   < d[v][1]){
					d[v][1] =   ④  ;
					pq.push({d[v][1], v, 1});
				}
			}
		}
	}
	
	cout <<   ⑤   <<  endl;
	return 0;
}
  1. ① 处应填：
    • A. 0
    • B. 1
    • C. -1
    • D. false
  2. ② 处应填：
    • A. d[u][!used]
    • B. d[u][used]
    • C. d[t][used]
    • D. INF
  3. ③ 处应填：
    • A. d[v][1]
    • B. d[v][used]
    • C. d[u][used]
    • D. d[v][0]
  4. ④ 处应填：
    • A. d[v][0]
    • B. d[v][1]
    • C. d[u][0]
    • D. d[u][1]
  5. ⑤ 处应填：
    • A. d[t][1]
    • B. d[t][0]
    • C. min(d[t][0], d[t][1])
    • D. d[t][0]+d[t][1]

T20 最优测试

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

以下程序实现了工厂的目标，包含两部分：

  1. 确定 \(w\) 的最小值，并设计最优测试方案；
  2. 根据测试结果推断存在缺陷的生产线。该程序确定 \(w\) 最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此 \(w\) 轮测试的可能结果数不应少于生产线数量。

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

试补全程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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 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) {
	// === 第 1 步：求最小 w === 
    int w = 1;
    while (  ① ) { 
        ++w;
    }
    cout << w << endl;
    
    // === 第 2 步：生成测试方案 === 
    vector<vector<int>> code(n, vector<int>(w, 0));
    int idx = 0;
    for (int ones = 0; ones <= k && idx < n; ++ones) {
        vector<int> bits(w, 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);
            }
        }
    }
    
    // === 第 3 步：调用测试接口 === 
    int signature = test_subset(plan);
    
    // === 第 4 步：结果解码 === 
    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;
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    int ans = solve(n, k);
    cout << ans << endl;
    return 0;
}
  1. ① 处应填：
    • A. (1<<w)<n
    • B. count_patterns(w,k) < n
    • C. count_patterns(k,w) < n
    • D. comb(w,k) < n
  2. ② 处应填：
    • 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)
  3. ③ 处应填：
    • A. (j>>i) & 1
    • B. (i>>j) & 1
    • C. code[i][j] == 1
    • D. code[j][i] == 1
  4. ④ 处应填：
    • A. (signature >> i) & 1
    • B. (signature >> i) ^ 1
    • C. signature | (1<<i)
    • D. (signature >> i) | 1
  5. ⑤ 处应填：
    • A. is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())
    • B. code[j] == sig_bits
    • C. plan[j] == sig_bits
    • D. code[j][i] == sig_bits[i]