在升序数组 nums 中寻找目标值 target,下列程序可以填入的是( )
查看答案与解析
nums数组是升序的,我们从中找target,采用二分查找,所以这个空应该是:mid取left位置和right位置的中间位置,所以为mid=(right-left)//2+left , 还需要注意整除。
在升序数组 nums 中寻找目标值 target,下列程序可以填入的是( )
nums数组是升序的,我们从中找target,采用二分查找,所以这个空应该是:mid取left位置和right位置的中间位置,所以为mid=(right-left)//2+left , 还需要注意整除。
500个病毒样本中,已知有一个是病毒检测呈阳性,用试纸测试阳性病毒以后,试纸在3天以后会变色,用试纸测试时间不计,三天以后要出结果,请问最少用多少个试纸能够找出哪一个病毒样本有毒()
可以考虑分治,把500个样本分成两组,每组250个,进行测试,这样的话可以排除250个阴性样本,然后再把剩下的250个样本分成两组,继续进行上述操作,这样的话可以每次排除掉当前一般样本,所以9次即可得到答案。
一名收银员,给顾客找零,找零的目标是给出确定金额的同时,使用尽可能少的硬币。有不同面额的硬币:1分,5分,10分,25分.如果需要给顾客准确的零钱77分,同时使用最少的硬币下列程序中横线应该填写( )。
因为要用尽可能少的硬币,对于coins数组,从大到小排序之后取用,如果当前给顾客的领钱,可以用coin,那么就amount-=coin,否则就看下一个coin。
下列程序是素数筛的程序,横线处应该填上( )。
第7行判断如果当前i是质数,则i的倍数都不是质数,所以这个地方是要枚举i的所有的倍数,注意右边界。
下面程序是埃氏筛的一个实现,横线处应该填写( )。
第5行判断如果当前i是质数;则i的倍数都不是质数,所以这个地方是要枚举i的所有的倍数,注意右边界。
下列程序中,使用了二分查找算法,横线处应该填写的是()。
首先排除C和D,应该是要整除才对,mid应该要取low和high的中间位置,所以应该是(low+high)//2。
正整数1024的所有约数的和为多少( )。
1024=210,所以约数和为(20+21+22+23……+210)=211−1。
下面程序是对n!进行唯一分解,横线处应该填入的是( )。
11行用math.factorial函数计算阶乘,阶乘传参为n,枚举2~n的所有数字,对于每个数字进行拆分,第4行填写:如果当前的n是i的倍数就记录答案,然后n//i,因为n可能包含多个i,所以用while循环。
假设有⼀些物品,每个物品都有⾃⼰的重量,我们需要将这些物品装⼊箱⼦中,每个箱⼦也有⾃⼰的重量限制。贪⼼算法每次都选择重量最轻的物品放⼊当前最轻的箱⼦中,如果箱⼦可以装下,就放⼊;如果箱⼦不能装下,就尝试下⼀个箱⼦,直到找到可以放⼊的箱⼦。下列贪⼼算法程序中,横线处应该填⼊的是( )。

boxes按照箱子的重量限制排序,items也从小到大排序,定义标记数组taken,枚举每个物品,然后标记已经访问过,然后枚举所有的箱子,如果当前箱子的剩余容量能放开当前物品,则放入当前箱子中,并更新当前箱子的容量,且boxes[j][1]表述的可能是编号,所以不用动。
下列归并算法程序中,横线处应该填入的是( )。
merge_sort函数是递归分的过程,merge函数是合并两个有序序列的过程,对于left和right这两个数组合并,所以应该是i<left的长度,j<right的长度。
下列快速排序算法中,横线处应该填入的是( )。
p是基准值,接下来我们要把比p小的值放到p的左边,比p大的放到p的右边,p的取值应该是arr数组中的随意一个值即可,ABC选项都有越界的风险,所以D最合适。
下列二分枚举算法中,{ }处应该填入的程序是({}不算做程序的一部分)( )。
对于有序序列arr,从中找x的位置,判断arr[mid+1]是不正确的,所以排序AB,然后如果arr[mid]==x,应该是找到了x的位置,直接return mid即可。
下面代码是寻找水仙花数的程序,横线处应该填写的代码是( )。【是指一个n位数(n≥3),其每位数字的n次幂之和等于它本身】
str_num是把num转成string类型的,也就是要拆位,num_digits是位数。
应该是要枚举所有位数字str_num,然后计算他的(num_digits)次方 。
对于正整数n,欧拉函数f(n),表示小于或等于n的正整数中与n互质的数的数目,例如f(8)=4。f(100)=( )。
找互质的数,不如找不互质的数字,也就是gcd不等于1的情况,也就是把100质因数分解2252,也就是说2的倍数和5的倍数都是和100不互质的,2的倍数有50个,5的倍数有20个,2和5的公倍数被计算了两次,所以再考虑10的倍数,一共10个,剩下40个与100互质的数字。
下列程序输出的是( )。
temp取第一个字符,然后继续递归,所以最后输出的结果是倒序输出。
(-1) mod 127和126 mod 127 的结果是一样的
取模和取余是不一样的,取模正数之后应该是一个非负数,应该是126。
一个数的反码,实际上是这个数对于一个模的同余数
1的反码表示是1111 1110。在不看符号位的情况下,111 1110=126。
-1在模127的情况下,和126同余,也就是(-1) ≡ 126 (mod 127)
而我们考虑2-1,其实是等价于2+126 (mod 127)
所以一个数的反码,实际上是这个数对于一个模的同余数
1997和615用欧几里得算法计算最大公约数的过程如下:
欧几里得算法也是辗转相除法,两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数
欧几里得算法适用于实数
欧几里得算法也是辗转相除法,一直在用取余操作,而实数没法取余。
每个大于1的整数可以唯一地写成质数的乘积的形式
唯一分解定理概念:任意大于等于2的整数,都可以唯一分解位若干个质数的幂次方的乘积的形式。
贪婪算法的复杂度通常是线性的,即O(n),其中n是输入的大小
宏观考虑的话,在不考虑其他如排序这样的运算的情况下,贪心算法通常是线性的,就是一次考虑每一个物品的最优情况即可。
归并排序的时间复杂度为O(n log n)
归并排序是基于分治思想的,时间复杂度为O(nlogn)。
根据同余计算,可以推导出(a∗b)%m=(a%m∗b%m)%m
乘法同余定理概念式。
二分查找算法的复杂度通常表示为O(log n),其中n是数组的长度
二分查找的时间复杂度为O(logn)。
def(十六进制) = 103231(五进制)
def(16进制)=3567(10进制)= 103232(5进制)
小杨的武器
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有n种不同的武器,他对第i种武器的初始熟练度为c。
小杨会依次参加m场战斗,每场战斗小杨只能且必须选择一种武器使用,假设小杨使用了第i种武器参加了第j场战斗,战斗前该武器的熟练度为ci′,则战斗后小杨对该武器的熟练度会变为ci′+a。需要注意的是,aj可能是正数,0或负数,这意味着小杨参加战斗后对武器的熟练度可能会提高,也可能会不变,还有可能降低。
小杨想请你编写程序帮他计算出如何选择武器才能使得m场战斗后,自己对n种武器的熟练度的最大值尽可能大。
输入格式
第一行包含两个正整数n,m,含义如题面所示。
第二行包含n个正整数c1,c2,...,cn,代表小杨对武器的初始熟练度。
第三行包含m个正整数a1,a2,...,am,代表每场战斗后武器熟练度的变化值。
输出格式
输出一个整数,代表m场战斗后小杨对n种武器的熟练度的最大值最大是多少。
输入样例
输出样例
一种最优的选择方案为,第一场战斗小杨选择第一种武器,第二场战斗小杨选择第二种武器。

对于全部数据,保证有1≤n,m≤105,−104≤ci,ai≤104。
我们想让武器熟练度最大值尽可能大,所以我们可以贪心考虑把原本的最大值,加上所有的正的熟练度,这样他就会变得最大。
流程:读入n和m,然后读入一个字符串,这个字符串就是c的信息,我们转成int类型,并找出其中的最大值mx,然后再读入一个字符串,这个字符串就是a的信息,我们把这个字符串转成int类型,判断a数组,如果当前熟练度增加值为正数,则累加到最大值mx上。
特别的,如果n==1,也就是只有一个武器,所以每次只能用这一个,这种情况下即使是负数,也要累加上。
挑战怪物
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨正在和一个怪物战斗,怪物的血量为h,只有当怪物的血量恰好为 0 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式:
·物理攻击。假设当前为小杨第i次使用物理攻击,则会对怪物造成2i−1点伤害。
·魔法攻击。小杨选择任意一个质数x(x不能超过怪物当前血量),对怪物造成x点伤害。由于小杨并不擅长魔法,他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物,如果能,小杨想知道自己最少需要多少次攻击。
输入格式
第一行包含一个正整数t,代表测试用例组数。
接下来是t组测试用例。对于每组测试用例,第一行包含一个正整数h,代表怪物血量。
输出格式
对于每组测试用例,如果小杨能够击败怪物,输出一个整数,代表小杨需要的最少攻击次数,如果不能击败怪物,输出 -1。
输入样例
输出样例
对于第一组测试用例,一种可能的最优方案为,小杨先对怪物使用魔法攻击,选择质数 5 造成 5 点伤害,之后对怪物使用第 1 次物理攻击,造成21−1=1 点伤害,怪物血量恰好为 0,小杨成功击败怪物。

对于全部数据,保证有1≤t≤10,1≤h≤105。
考虑到物理攻击一定是1,2,4,……2i−1,这样枚举的,所以魔法攻击放到什么位置其实没有影响。
所以我们考虑如果当前x是质数,直接减质数结束即可,如果不是质数的话,就使用物理攻击即可。
流程:先用质数筛求质数,然后输入t,输入x,我们需要维护当前的物理攻击的值tmp,也就是1 2 4 ……,如果当前的x是质数,则直接结束,如果不是质数,则x-=tmp。
然后进行判断,如果x==0,则结束输出答案,如果x<0,则是没有答案的情况,输出-1