GESP-Python五级 题库
假设我们有两个数 a = 38 和 b = 14 ,它们对模 m 同余, 即a ≡ b (mod m)。以下哪个值不可能是 m?
下面的程序中,x,y都是正整数,完成的算法是( )
下面程序是对2024进行唯一分解,最后的结果应该是( )。
下面程序是对n!进行唯一分解,横线处应该填入的是( )。
11行用math.factorial函数计算阶乘,阶乘传参为n,枚举2~n的所有数字,对于每个数字进行拆分,第4行填写:如果当前的n是i的倍数就记录答案,然后n//i,因为n可能包含多个i,所以用while循环。
一个数的反码,实际上是这个数对于一个模的同余数
1的反码表示是1111 1110。在不看符号位的情况下,111 1110=126。
-1在模127的情况下,和126同余,也就是(-1) ≡ 126 (mod 127)
而我们考虑2-1,其实是等价于2+126 (mod 127)
所以一个数的反码,实际上是这个数对于一个模的同余数
下面的Python代码能实现十进制正整数N转换为2、8、10、16,可适用于16进制以内进制。其中n和ds分别表示将转换的数以及目标进制。( )
这段Python代码实现了将十进制正整数n 转换为指定的目标进制ds 的功能。它适用于目标进制在16进制以内的情况。具体步骤如下:
输入处理:从标准输入读取两个整数n 和ds,分别表示要转换的数和目标进制。
字符映射:使用 digDict 字典将十进制数的每一位数映射为对应的目标进制字符(0-9对应’0’-‘9’,10-15对应’A’-‘F’)。
转换过程:通过循环,将十进制数n 除以目标进制ds,并将得到的余数对应的字符插入到结果字符串rst的开头,直到n 变为0。
输出结果:最后打印出转换后的结果字符串rst,即为目标进制下n 的表示。
Python代码 print(sorted(range(10),key=lambda x:x%5)) 执行时将报错。( )
print(sorted(range(10), key=lambda x: x % 5)) 在执行时不会报错。
range(10) 生成了一个包含0到9的整数序列。
sorted() 函数对这个序列进行排序,排序的依据是 key=lambda x: x % 5,即按照每个元素对5取余的结果来排序。因为对于0到9的数字,它们对5取余的结果是 [0, 1, 2, 3, 4, 0, 1, 2, 3, 4],所以排序后的结果是 [0, 5, 1, 6, 2, 7, 3, 8, 4, 9]。print() 函数会输出这个排序后的列表。
Python代码 print(sorted(list(range(10)), key = lambda x:x % 5)) 执行后将输出 [0, 5, 1,6, 2, 7, 3, 8, 4, 9] 。( )
数字移动
时间限制:3.0 s
内存限制:512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列 A = A₁ , A₂, … …A_N,序列 A 恰好包含成对不同的正整数。形式化地,对于任意 1 ≤ i ≤ N ,存在唯一一个 j 满足 1 ≤j≤ N, i≠ j, A_i = A_j。
小 A 希望每对相同的数字在序列中相邻,为了实现这一目的,小 A 每次操作会选择任意 i (1 ≤ i ≤ N),将当前序列的第 i 个数字移动到任意位置,并花费对应数字的体力。
例如,假设序列 A = {1 , 2, 1 , 3, 2, 3},小 A 可以选择 i = 2,将 A₂ = 2 移动到 A₃=1 的后面,此时序列变为{1 , 1 , 2, 3, 2, 3},耗费 2 点体力。小 A 也可以选择 i = 3,将 A₃=1 移动到A₂ = 2 的前面,此时序列变为{1 , 1 , 2, 3, 2, 3},花费 1 点体力
小 A 可以执行任意次操作,但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 X,使得他能够在每次花费的体力均不超过 X 的情况下令每对相同的数字在序列中相邻。
输入格式
第一行一个正整数 N,代表序列长度,保证 N 为偶数。
第二行包含 N 个正整数 A₁ , A₂ , · · . , A_N,代表序列 A。且对于任意 1 ≤ i ≤ N,存在唯一一个j 满足1 ≤ j ≤ N, i≠ j, A_i= A_j。
数据保证小 A 至少需要执行一次操作。
输出格式
输出一行,代表满足要求的 X 的最小值。
样例
输入样例
输出样例
仅移动数值1即可完成全部配对,所有操作体力≤1,最小X=1。 数据范围 对于40%的测试点,保证 1 ≤ N, A_i ≤ 100。 对于所有测试点,保证 1 ≤ N, A_i ≤ 10⁵。
# 输入n和a数组 n = int(input()) a = [] while len(a) < n: a.extend(map(int, input().split())) # 答案的上下界 left, right = 0, 1000000 ans = 1000000 # 二分搜索 while left <= right: # 考虑mid的力气能否完成任务 mid = (left + right) // 2 # 筛选出所有大于mid的数字 b = [x for x in a if x > mid] # 先假设能够完成任务 possible = True for i in range(0, len(b), 2): # 如果两个相同且大于mid的数字 ,中间还有其它的大于mid的数字 ,则本任务无法完成 # 以 (1 2 1 3)为例 ,两个1之间存在2。假设最大只能挪动1 ,则不论如何两个1之间的2不会被挪动,最终无法完成配对 if b[i] != b[i+1]: possible = False break # 如果能够成功 ,则尝试更小的mid if possible: ans = mid right = mid - 1 else: left = mid + 1 print(ans)
平均分配
题目描述
小 A 有2n 件物品,小 B 和小 C 想从小 A 手上买走这些物品。对于第 i件物品,小 B 会以bi 的价格购买,而小 C 会以 ci的价格购买。为了平均分配这 2n件物品,小 A 决定小 B 和小 C 各自只能买走恰好n 件物品。你能帮小 A 求出他卖出这 2n件物品所能获得的最大收入吗?
输入格式
第一行,一个正整数n 。
第二行, 2n个整数b1,b2,...,b2n 。
第三行,2n 个整数 c1,c2,...,c2n。
输出格式
一行,一个整数,表示答案。
输入样例 1
3
1 3 5 6 8 10
2 4 6 7 9 11
输出样例 1
36
输入样例 2
2
6 7 9 9
1 2 10 12
输出样例 2
35
数据范围
对于20 % 的测试点,保证1 ≤n≤8。
对于另外20 % 的测试点,保证 0≤bi≤1,0≤ci≤1 。
对于所有测试点,保证 1 ≤n≤105,0≤bi≤109,0 ≤ci≤109 。
n = int(input()) b = list(map(int, input().split())) c = list(map(int, input().split())) d = [c[i] - b[i] for i in range(2 * n)] print(sum(b) + sum(sorted(d)[n:]))
小杨的幸运数
时间限制:5.0 s
内存限制:128.0 MB
问题描述
小杨认为,所有大于等于a的完全平方数都是他的超级幸运数。
小杨还认为,所有超级幸运数的倍数都是他的幸运数。自然地,小杨的所有超级幸运数也都是幸运数。
对于一个非幸运数,小杨规定,可以将它一直+1,直到它变成一个幸运数。我们把这个过程叫做幸运化。例如,如果a=4,那么4是最小的幸运数,而1不是,但我们可以连续对1做3次+1操作,使其变为4,所以我们可以说,1幸运化后的结果是4。
现在,小样给出N个数,请你首先判断它们是不是幸运数;接着,对于非幸运数,请你将它们幸运化。
输入描述
第一行 2 个正整数a,N。
接下来N行,每行一个正整数x,表示需要判断(幸运化)的数。
输出描述
输出N行,对于每个给定的x,如果它是幸运数,请输出lucky ,否则请输出将其幸运化后的结果。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
1虽然是完全平方数,但它小于a,因此它并不是超级幸运数,也不是幸运数。将其进行3次+1操作后,最终得到幸运数4。
4是幸运数,因此直接输出 lucky 。
5不是幸运数,将其进行3次+1操作后,最终得到幸运数8。
9是幸运数,因此直接输出 lucky 。
样例输入 2
样例输出 2
数据规模
对于30%的测试点,保证a,x≤100,N≤100 。
对于60%的测试点,保证a,x≤106。
对于所有测试点,保证a≤1000001;保证N≤2×105;保证1≤x≤1000001。
a, n = input().split()
a, n = int(a), int(n)
max_lucky = 1001 ** 2 + 10
is_lucky = [False for i in range(max_lucky + 1)]
next_lucky = [-1 for i in range(max_lucky + 1)]
for i in range(1, max_lucky):
if i >= a and int(i ** 0.5) ** 2 == i:
is_lucky[i] = True
for j in range(i + i, max_lucky, i):
is_lucky[j] = True
for i in range(max_lucky - 1, 0, -1):
if is_lucky[i]:
next_lucky[i] = i
else:
next_lucky[i] = next_lucky[i + 1]
for i in range(n):
x = int(input())
assert 1 <= x <= 10 ** 6 + 1
if next_lucky[x] == x:
print("lucky")
else:
print(next_lucky[x])烹饪问题
时间限制:1.0 s
内存限制:128.0 MB
问题描述
有N种食材,编号从0至N-1,其中第i种食材的美味度为ai。
不同食材之间的组合可能产生奇妙的化学反应。具体来说,如果两种食材的美味度分别为x和y,那么它们的契合度为x and y。
其中,and运算为按位与运算,需要先将两个运算数转换为二进制,然后在高位补足0,再逐位进行与运算。例如,12与6的二进制表示分别为 1100 和 0110 ,将它们逐位进行与运算,得到 0100 ,转换为十进制得到4,因此12 and 6=4。在 C++ 或 Python 中,可以直接使用 & 运算符表示与运算。
现在,请你找到契合度最高的两种食材,并输出它们的契合度。
输入描述
第一行一个整数N,表示食材的种数。
接下来一行N个用空格隔开的整数,依次为a0,…,aN-1,表示各种食材的美味度。
输出描述
输出一行一个整数,表示最高的契合度。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
可以编号为1,2的食材之间的契合度为2 and 3=2,是所有食材两两之间最高的契合度。
样例输入 2
样例输出 2
样例解释 1
可以编号为3,4的食材之间的契合度为10 and 13=8,是所有食材两两之间最高的契合度。
数据规模
对于40%的测试点,保证N≤1000;
对于所有测试点,保证N≤106,0≤ai≤2147483647。
n = int(input()) a = list(map(int, input().split())) a = [0] + a def sort_(l, r, k): while l <= r: while (l <= r) and (a[l] >> k & 1): l += 1 while (l <= r) and (not (a[r] >> k & 1)): r -= 1 if l <= r: a[l], a[r] = a[r], a[l] l += 1 r -= 1 return r ans = 0 for i in range(31, -1, -1): j = sort_(1, n, i) if j >= 2: ans |= 1 << i n = j print(ans)