单项选择题

1. 有5个红色球和5个蓝色球，它们除了颜色之外完全相同。将这 10 个球拍成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法?
A. 25
B. 30
C. 6
D. 120

答案:C
解析: 先排列5个红球，完全相同，所以只有一种方案，5个红球算上左右两边会有6个空位，蓝球插空放入，不能相邻，一个空只能一个，所以6选5，C(6,5)==6

2. 在 KMP 算法中，对于模式串 P=”abacaba”，其 next 数组(next[i] 定义为模式串 P[0…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
解析:next[i]的值是字串的最长相等前后缀的长度，前缀指不包含最后一个字符的头部子串，后缀指不包含第一个字符的尾部子串
0:’a’没有前后缀，next[0]=0
1:’ab,前缀’a’后缀’b’，没有公共部分,next[1]=0
2:’aba,前缀{“a”,”ab”},后缀{“a”,ba”},最长公共”a’,next[2]= 1;
3:”abac”,前缀{“a”,”ab”,”aba”}，后缀{“c”,”ac”,”bac”}。无公共部分。next[3]=0
至此已经可以选出A选项

3. 对一个大小为 16(下标 0-15)的数组上构建满线段树。查询区间[3,11]时，最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?
A. 7
B. 8
C. 9
D. 10

答案:B
解析: 根节点区间[0，15]，目标区间[3.11]在内部，需要查找子树。完整的线段树结构如下图(圆圈内是节点编号，红色标注的节点是查询过程中涉及的)
最终用区间[3,3],[4,7],[8,11]拼出[3,11]。
-共查询过[0,15],[0,7],[8,15],[0,3],[2,3],[3,3],[4,7],[8,11]共八个区间节点

4. 将字符串”cat”，”car”，”cart”，”case”，”dog”，”do”插入一个空的 Trie 树(前缀树)中。构建完成 Trie 树(包括根节点)共有多少个结点?
A.8
B.9
C.10
D.11
答案:D
解析:初始一个root节点，
插入cat,root->c->a->t;
插入car,root->c->a已经存在，新增a->r
插入cart,root->c->a->r已经存在，新增r->t
插入case,root->c->a已经存在，新增a->s->e
插入dog,新增root->d->o->g
插入do,root->d->o已经存在
共11个节点

5. 对于一个包含n个结点和 m 条边的有向无环图(DAG)，其拓扑排序的结果有多少种可能?
A. 只有一种
B. 最多n种
C. 等于n-m种
D. 以上都不对
答案:D
解析:图是一条链时拓扑唯一，如果n个节点0条边，有n!种，A,B,C均错误

6. 在一个大小为 13 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 H(key)=keymod 13。依次插入关键字 18，26，35，9，68，74。插入74后，它最终被放置在哪个索引位置?
A. 5
B. 7
C. 9
D. 11
答案:D
解析:模拟即可，
鸌出入18，18%13=-5，放在位置5
插入26，26%13==0，放在位置0
煇了到实 核桃编i
插入35，35%13==9，放在位置9
插入9，9%13=-9，不为空，后移10空，放在位置10
插入68，68%13==3，放在位置3
插入74，74%13=9，不为空，后移找到空位11，放在位置11

7. 一个包含8个顶点的完全图(顶点的编号为1倒8)，任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点3和了之间的边权重为7-3=4。该图的最小生成树总权重是多少?
A.7
B.8
C.9
D.10
答案:A
解析:边权全为1的边,(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8)做最小生成树，权重为7

8. 如果一棵二叉搜索树的后序遍历序列是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
解析:后序遍历，未尾6是根，小于6的(2，5，4)是左子树，大于6的(8，12，10)是右子树
左子树后序(2，5，4)，4为根，小的2是左，大的5是右
右子树后序(8，12，10)，10为根，小的8是左，大的12是右
瘗在前序遍历根左右，结果为(6，4，2，5，10，8，12)

9. 一个 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 == 19->43
物品 2+3+4+5 == 18->41
物品 1+3+4+5 ==20->44
物品 2+3+4+5 == 18->41
其他方案只会减少物品，放弃，所以最大44

10. 在一棵以结点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，LCA(12,18)为4，则1为4的祖先，LCA(12,1)不可能出现

11. 递归关系式 T(n)= 2T(n/2)+O(n²)描述了某个分治算法的时间复杂度。 请问该算法的时间复杂度是多少?
A. O(n)
B. O(nlogn)
c. O(n²)
D. O(n²logn)
答案: C
解析: 主定理:T(n)=aT(n/b)+f(n)，递归式代入，a-2,b==2,f(n)== O(n^2)
比较 f(n)和n^log_ba大小， n^log_ba == n^log₂2==n,n^2增长远大于n,代入主定理，
如果 f(n)= Ω(n^(log_b a+ ε)) 对于某个常数 ε>0 成立，则T(n)=θ(f(n))。
f(n)=n²，而n^(log_b a+ε)=n^(1+ε)。取ε=1，此时n²=Ω(n²)
所以，T(n)=θ(f(n))=θ(n²)

12. 在一个初始为空的最小堆(min-heap)中，依次插入元素 20,12,15,8,10,5。然后连续执行两次”删除最小值”(delete-min)操作。请问此时堆顶元素是什么?
A. 10
B. 12
C. 15
D. 20
答案:A
解析:最小堆堆顶为最小值，连续删除两次后堆顶为第三小，5->8->10

13. 1到 1000 之间，不能被 2、3、5 中任意一个数整除的整数有多少个?
A. 266
B. 267
C. 333
D. 734
答案:A
解析:容斥原理，首先考虑能被2，3，5分别整除
2:1000/2==500 3:1000/3 == 333 5:1000/5 == 200
接下来能被2,3,5的两个整除
翳,3:1000/6==166 2,5:1000/10==100 3.5:1000/15==66
最后能同时被2，3，5整除
陛会,3,5:1000/30== 33
根据容斥原理，能被2，3，5任意数整除的答案为:N(2)+N(3)+N(5)-(N(6)+N(10)+N(15)+ N(30)=734
所以不能被任意一个数整除的方案为1000-734==266

14. 斐波那契数列的定义为 F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)。使用朴素递归方法计算 F(n)的时间笃型记杂度是指数级的。而使用动态规划(或迭代)方法的时间复杂度是线性的。造成这种巨大差异贑员到和根本原因是?
A. 递归函数调用栈开销过大
B. 操作系统对递归深度有限制
C. 朴素递归中存在大量的重叠子问题未被重复利用
D. 动态规划使用了更少的数据存储空间
答案:C
解析:朴素递归因为重复计算，呈指数级增长，导致效率过低

15. 有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
解析:带截止时间的任务调度，目标是最小化总惩罚，等价于最大化能按时完成的任务的总处理时长，贪心策略选择最早截止优先，越紧急的任务越应该先做，这样才能给其他任务留出更多的时间窗口

阅读程序

阅读下列程序，回答问题。

cpp

#include 

#include 

#include 

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;

}

代码解析:这段代码使用深度优先搜索(DFS)生成所有1到n的排列，但有一个限制:在排列中，相邻的两个数不能是连续递增的(即不能出现p[k]==p[k-1]+1的情况)。代码统计满足条件的排列数目。

16. 当输入的 n=3 的时候，程序输出的答案为 3。
A.正确
B.错误
答案: A
解析:合法的全排列有132、213、321共3个

17. 在 dfs 函数运行过程中，k的取值会满足 1<=k<=kn+1。
A. 正确
B.错误
答案: A
解析:k表示当前正在填充排列的第k个位置，当k=n+1时表示n个元素都填充完毕。

18. 删除第 19 行的”flag[i]=false;”，对答案不会产生影响。
A.正确
B.错误
答案: B
剁月他析:第19行是回溯操作:恢复数字i的未访问状态，以便在其他分支中使用。

19. 当输入的 n=4的时候，程序输出的答案为()。
A. 11
B. 12
C. 24
D. 9
答案: A
解析:合法的全排列有1432、2143、2413、2431、3142、3214、3241、3412、3421、4132、4213、431共11个。

20. 如果因为某些问题，导致程序运行第 25 行的 dfs 函数之前，数组p的初值并不全为0，则对程序的影响是()。
A. 输出的答案比原答案要小
B. 无法确定输出的答案
C. 程序可能陷入死循环
D. 没有影响
答案:D
解析:数组p用于存储当前排列，在DFS过程中会被覆盖。

21. 假如删去第 14 行的“if(flag[i])continue;”，输入3，得到的输出答案是()。
A. 27
B. 3
C. 16
D. 12
答案:C
解析:第14行是检查数字i是否已被使用。如果删除，则允许重复使用数字，可根据第1位数字进行分类计算，有111、113、131、132、133、211、213、221、222、311、313、321、32疳场行一、3 3 1、3 3 2、3 3 3共16个。

阅读下列程序，回答问题。

cpp

#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=l;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);茵59

	if(t == 1){

		guess1(n);

	} else {

		guess2(n);

	}

	return 0;

}

(注意:下述的“猜测数”为调用 check 函数的次数(即 cnt check 的值);“猜测正确”的含义为 assert ans 函数 return true (执行第 25 行所在分支)的情况;所有输入保证1 <= k <= n。)

代码解析: 这段代码模拟了两个猜测策略(guess1和 guess2)来寻找一个数字k。check(h)函数模拟检查数字h是否大于等于k，如果是则标记“损坏”(cnt broken增加)，并且最多允许损坏两次。assert ans(h)函数用于验证h是否等于k。
guess1: 线性扫描从1到n，逐个检查，直到找到第一个满足check(i)为真的i，然后验证。
guess2: 采用类似“跳跃”的方式，先确定一个步长w，然后从w开始跳跃检查，一旦发现损坏，则回退一段进行精细查找。

判断题

22. 当输入为“65 1”时，猜测次数为 5;当输入“65 2” 时，猜测次数为 3。
A. 正确
B. 错误
答案: A
解析:对于guess1，从1开始检查直到5，检查次数为5。对于guess2，初始时w=ti=nh=3，check(3)返回false，然后ti=2，nh=5，check(5)返回true，接着j遍历4，check(4)返回false，然后直接验证5共检查3次。

23. 不管输入的n和k具体为多少，t=2时的猜测数总是小于等于 t=1时的猜测数。
A. 正确
B. 错误
答案: B
解析: 当n=6，k=1时，guess1只需检查1次，而guess2初始检查的数字为3，第二次才检查1，共检查2次。

24. 不管 t=1或 t=2，程序都一定会猜到正确结果。
A. 正确
B. 错误
答案: 对
解析: guess1是线性扫描，一定能找到正确结果，guess2跳跃后回退查找，最多损坏2次，也能找到正确结果。

25. 函数 guess1在运行过程中，cnt broken 的值最多为()。
A. 0
B. 1
C. 2
D. n
答案: B
解析:guess1线性扫描，直到找到第一个>k的值(即k本身)，此时cntbroken增加1。

26. 函数 guess2 在运行过程中，最多使用的猜测次数的量级为()。
A. Ο(n)
B. O(n²)
c. Ο(\sqrt{n})
D. Ο(logn)
答案: C
解析:内层回退的步长最多为w，而w是最小的正整数满足 w*(w+1)/2>n,所以w的量级是Vn 。

27. 当输入的 n=100 的时候，代码中 t=1和 t=2分别需要的猜测次数最多分别为()。
A. 100, 14
B. 100, 13
C. 99,14
D. 99, 13
答案:A
解析:guess1:最坏情况k=100，需要100次。guess2:最坏情况k=14，初始w=ti-nh=14，此时check(14)返回true，需回退，然后i从1遍历到13，共check(13)次，总check次数为14次。

阅读题

cpp

#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=l;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=l; 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-1l;

		} else {

			ans1[newcnt1++]=ans1fil;

			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;

}

代码解析:程序用于求解一个整数方程:给定n组系数 k_i和指数 p_i，以及范围m，找出所有整数解(x1,x2,.., xn)其中每个xi在[1,m]范围内，满足方程k1*x1^{p1}+k2*x2^{p2} ++ kn *xn^{pn}=0。。。
程序用 meetin the middle 思想，将n个变量分为前后两半，将时间复杂度从 0(m”) 降为 O(mnP)。具体做法为，用 DFS 分别计算两部分所有可能的表达式值(存储与 ans1和 ans2)，然后对ans1 排序并去重，记录每个值的出现次数;对 ans2 排序后，使用双指针法统计ans1和ans1中值和为零的组合数，累加出现次数。

判断题

28. 删除第 51行的“std::sort(ans2.begin(),ans2.end();”后，代码输出的结果不会受到影响。
A. 正确
B. 错误
答案: B
解析:后续循环(第54-59行)使用双指针方法在排序后的 ans1 和 ans2 中查找匹配值。如果ans2 未排序，则las 指针的递增将无法正确匹配，导致计数错误。

29. 假设计算过程中不发生溢出，函数 mpow(x,k)的功能是求出 x”的取值。
A. 正确
B.错误
答案:正确
解析:若抛开 int 容易溢出的问题，函数 mpow(x，k)是标准的快速幂实现。

30. 代码中第 39 行到第 50 行的目的是为了将 ans1 数组进行“去重” 操作。()
A.正确
B.错误
答案:正确
解析:代码第39行到第50行的目的是对 ans1 数组进行排序并压缩相等段，方便后续计数，即去重后猄场交人录每个唯一值的出现次数(存储在 cntans1 中)。

选择题

31. 当输入为“31512-1212”时，输出结果为()
A. 4
B. 8
C. 0
D. 10
答案:B
解析:即求 x^2-y^2+z^2=0 的解，x,y,z取值范围在[1,15]。满足条件的三元组有(3,5,4),(4,5,3),(6,10,8),(8,10,6),(9,15,12),(12,15,9),(5,13,12),(12,13,5)，共8组。

32. 记程序结束前p数组元素的最大值为P，则该代码的时间复杂度是()
A. O(n)
B. O(mⁿlogmⁿ)
C. O(m^n/2logm^n/2)
D. O(m^n/2(logm^n/2 + logP)
答案:D
解析:
代码的时间复杂度主要来自以下两方面:
DFS生成状态:每次调用处理n/2个变量，对于每个变量，循环m次，O(m^n/2)。每次DFS中，mpow 调用时间复杂度为O(logP)。总时间复杂度 O(m^n/2log P)。
排序: O(m^n/2logm^n/2)
总时间复杂度: O(m^n/2(logm^n/2 + logP)

33.本题所求出的是()
A. 满足 α,b,c ∈ [1,m]的整数方程\(a^{3}+b^{3}=c^{3}\)的解的数量
B. 满足 α, b,c ∈「1,m|的整数方程\(a^{2}+b^{2}=c^{2}\)的解的数量
C. 满足 x_i ∈ [0,m]的整数方程\(\sum\limits_{i=1}^{n}k_{i}\cdot x_i^{p_{i}} = 0 \)的解的数量
D. 满足 x_i ∈ [1,m]的整数方程\(\sum\limits_{i=1}^{n}k_{i}\cdot x_i^{p_{i}} = 0 \)的解的数量

答案: D
解析:程序的功能是求解满足 x_i ∈ [1,m]的整数方程\(\sum\limits_{i=1}^{n}k_{i}\cdot x_i^{p_{i}} = 0 \)的解的数量。

完善程序

(一)完善程序第一题
(特殊最短路)给定一个含N个点、M 条边的带权无向图，边权非负。起点为S，终点为T。对于一条S到T的路径，可以在整条路径中，至多选择一条边作为“免费边”:当第一次经过这条被选中的边时，费用视为0;如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从S到T的最小总费用。
以下代码求解了上述问题。试补全程序。

cpp

#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, l 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;

}

代码解析:
分层图 Diikstra 求最短路。
d[i][0]表示到达节点i，尚未使用免费边的最小费用。
d[i][1]表示到达节点i，已经使用免费边的最小费用。
没有使用免费边的状态，可以转移到没有使用或者使用了转移边的状态而使用了免费边的状态，只能转移到使用了的状态。

34. ①处应填入()
A. 0
B. 1
c. -1
D. false
答案: A
解析:此处表示将起始状态入队。第一个变量表示费用，第一个变量表示点的编号，第三个变量表示是否使用了免费边，初始没有使用，故选 0。

35. ②处应填入()
A. d[u][!used]
B. d[u][used]
C. d[t][used]
D. INF
答案: B
解析:此处属于 Diikstra 中跳过某状态时的判断，当当前优先队列中记录的费用 dist 大于d数组记录的费用，d[u][used]时，说明 dist 不是最优的费用，故可以跳过。

36. ③处应填入()
A. d[v][1]
B. d[vlfused]
C. dlulused
D. d[v][0]
答案: B
解析:此处为本次不使用免费边的情况，used 的状态不会被改变，所以应该尝试用 d[ullusedl+w更新 d[v][used]，故选 B。

37. ④处应填入()
A. d[v][0]
B. d[v][1]
c. d[u][0]
D. d[u][1]
答案: C
解析:当 used==0时，可以考虑本次使用免费边，此时新费用为 d[u][0]+0，所以应该用 d[u][0]尝试更新 d[v][1]。

38. ⑤处应填入()
A. d[t][1]
B. d[t][0]
C. min(d[tlf0], d[t][1])
D. d[t][0] + d[t][1]
答案:C
解析:输出答案为S到T的最小费用，由于可以使用免费边，也可以不使用，故答案为d[t][0]和 d[t][1]取最小值。
为什么不选 A:初始化时，d数组只有 d[s][0]初始化为了0，其他值均初始化为极大值，考虑到S和T 可能重叠，故不能直接输出 d[t][1]。

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

以下程序实现了工厂的目标，包含两部分:i)确定w的最小值，并设计最优测试方案;i) 根据测试结果推断存在缺陷的生产线。该程序确定w最小值的方法为:由于不同的生产线故障时，测试应当返回不同的结果，因此w轮测试的可能结果数不应少于生产线数量。
test subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。
test subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。
试补全程序。

cpp

#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();

	cout << ans << endl;

	return 0;

}

代码解析:
程序分为四步
1. 确定最小测试轮数 w
2. 对n条生产线进行编码
3. 构造测试方案
4. 调用测试函数
5. 重新解码

39. ①处应填入()
A. (1 << w) < n
B. count patterns(w, k) < n
C.count patterns(k, w) < n
D.comb(w, k) < n
答案:B
解析:此处在计算最小的测试轮数 w。count patterns(w,k)是在计算长度为 w，且1的个数不超过k的不同的二进制串的总数，当 count patterns(w,k)>=n时，表示存在这样的二进制编码可以将n条生产线表示出来。所以循环进行的条件是count patterns(w, k) < n。

40. ②处应填入()
A. next permutation(bits.begin(), bits.end())
B. prev permutation(bits.begin(), bits.end())
C. next permutationlbits.begin(),bits.begin()+ones)
D. prev permutation(bits.begin(),bits.begin()+ones)
答案: B
解析:本处需要生成ones个1和w-ones个0的全排列，next permutation 函数可用于对某个序列綴生成下一个字典序的排列，直接调用 next permutation(bits.begin(),bits.end()) 即可。prev_permutation 是生成某个序列上一个字典序的排列，而我们初始状态已经是字典序最小的，会直接返回 false。

41. ③处应填入()
A. (j >> i) &1
B. (i >> j) &1
C. code[i][j] == 1
D. code[j][i] == 1
答案:D
解析:plan[i] 表示第i轮测试中包含的生产线编号。code[j] 存储第i条生产线的测试编码。当 code[j][i]==1表示第i条生产线参与第i轮测试，此时将j加入plan[i]。

42. ④处应填入()
A. (signature >> i)& 1
B. (signature >> i) ^ 1
C. signature (1 << i)
D. (signature >> i)|1
答案: A
解析:signature 是一个整数，它的二进制表示包含了所有测试轮次的结果。为了将这个整数解码成一个二进制串，我们需要逐位提取。最低位即第1轮(即i=0时)，i位的值，可以用(signature >>i)&1判断是否为 1，如果为 1，则需要记录在实际测试结果 sig_bits 中。

43. ⑤处应分别填入()
A. is_permutation(code[j].begin(), code[j].end(),sig_bits.begin()
B. code[i]== sig bits
C. plan[j] == sig_bits
D. code[j][i] == sig_bits[i]
答案: B
解析:sigbits 表示实际测试的结果，需要根据测试结果寻找匹配的生产线，为了找到与实际结果相匹配的生产线，我们需要遍历所有生产线j，并比较 code[j]是否与 sig_bits 完全相同。在 C++ 中，std::vector 类重载了 == 运算符，可以直接比较两个 vector 中的所有元素是否都相等。故选 code[i]== sig_bits 。

那年 • 今日

2024年 第十五届蓝桥杯完美通关