GESP-Python五级 题库
小杨想写一个程序来算出正整数N有多少个因数,经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。( )(2023年12月五级)
Python代码 print(sorted(list(range(10)), key = lambda x:x % 5)) 执行后将输出 [0, 5, 1,6, 2, 7, 3, 8, 4, 9] 。( )
Python的内置函数 sorted() 可以对支持 for-in 循环的 str 、 list 、 tuple 、 dict 、 set 排序,且是稳定排序。
数字移动
时间限制: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)
相等序列
时间限制:3.0 s
内存限制:512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列A = {A₁ , A₂ , · · ,A_N}。小 A 每次可以花费 1 个金币执行以下任意一种操作:
1. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i × P,P 为任意质数;
2. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i ÷ P,P 为任意质数,要求 A_i 能整除 P。
小 A 想请你帮他计算出令序列中所有整数都相同,最少需要花费多少金币。
输入格式
第一行一个正整数 N,含义如题面所示。
第二行包含 N 个正整数 A₁ , A₂ , · · ,A_N,代表序列 A。
输出格式
输出一行,代表最少需要花费的金币数量。
样例
输入样例
输出样例
数据范围
对于60%的测试点,保证 1 ≤ N, A_i ≤ 100。
对于所有测试点,保证 1 ≤ N, A_i ≤ 10⁵。
tokens = []
def get_val() :
while not tokens:
tokens.extend(input().split())
return int(tokens.pop(0))
# 一共有多少数
n = get_val()
# key:质数
# value:一个列表 ,num[p][exp]表示有多少数质因数分解后可以包含p^exp
# 因为一个数最大就到10^5 ,相当于是10w ,所以列表最多包含20个数肯定够用 ,即2^20
num = {}
for _ in range(n) :
# 统计一下各个输入数字有多少质因数
x = get_val()
d = 2
# 质因数必定小于根号x
tmp = x
while d * d <= tmp:
# 如果找到了一个数是x的因数
if tmp % d == 0 :
cnt = 0
# 那就一直除以这个数 ,并且更新x的质因数数目
# 这样一来剩下能够整除x的必定是质数
while tmp % d == 0 :
tmp //= d
cnt += 1
if d not in num:
num[d] = [0] * 20
# 数字x包含d^cnt ,更新状态
num[d][cnt] += 1
d += 1
# 如果x是质数
if tmp > 1 :
if tmp not in num:
num[tmp] = [0] * 20
num[tmp][1] += 1
ans = 0
for p in num:
counts = num[p]
# 计算有多少数字不包含这个质因数
counts[0] = n - sum(counts)
# 寻找中位数指数
# 也就是寻找一个指数e,使得一半的数字包含超过e次方的p,另一半不包含
pos = 0
median_exponent = 0
for j in range(20) :
pos += counts[j]
if pos * 2 >= n:
median_exponent = j
break
# 计算代价
for j in range(20) :
if counts[j] :
ans += counts[j] * abs(j - median_exponent)
print(ans)试题名称:数字选取
时间限制:1.0 s
内存限制:512.0 MB


n = int(input()) # p[0]、p[1]占位/置0,2~n初始标记为1(是质数) p = [1] * (n + 1) p[0] = p[1] = 0 # 只筛到根号n for i in range(2, int(n ** 0.5) + 1): if p[i] == 1: # i是质数,筛掉它所有倍数 # 从i*i开始,步长i for j in range(i * i, n + 1, i): p[j] = 0 # sum(p) 等于1~n内质数总个数 print(sum(p))
试题名称:有趣的数字和
时间限制:1.0 s
内存限制:512.0 MB


def cal2(n, p): """ 计算奇偶性为p的 0~n 的有趣的数之和,要求n为2^k - 1的形式 :return: 有趣的数量, 有趣的数之和 """ if n == 0: return 1 - p, 0 if n == 1: return 1, p return (n + 1) // 2, n * (n + 1) // 4 def cal(n, p): """ 计算奇偶性为p的 0~n 的有趣的数之和 :return: 有趣的数量, 有趣的数之和 """ if n <= 1: return cal2(n, p) x = 1 while x * 2 <= n: x *= 2 # 找出最大x=2^k,x-1=2^k-1 <= n cntl, sl = cal2(x - 1, p) # 剩下部分:最高位1去掉,剩余数位奇偶性相反 1-p cntr, sr = cal(n - x, 1 - p) # 总数 = 左半部分 + 右半部分 total_cnt = cntl + cntr # 总和 = 左半和 + 右半和 + 高位x 乘右边数字个数 total_sum = sl + sr + x * cntr return total_cnt, total_sum # 主程序 l, r = map(int, input().split()) # 0 ~ l-1 的符合条件数字总和 _, ansl = cal(l - 1, 1) # 0 ~ r 的符合条件数字总和 _, ansr = cal(r, 1) # [l, r] 区间和 = 0~r总和 - 0~l-1总和 print(ansr - ansl)
奖品兑换



# 接受小A持有的两种券的数量 n, m = map(int, input().split()) # 兑换1份奖品分别所需两种券的数量 a, b = map(int, input().split()) # 统一处理:把持有券、所需券都调整为 (少, 多) 的顺序,简化后续计算 n, m = min(n, m), max(n, m) a, b = min(a, b), max(a, b) def check(v): """ 检测手头的券能否兑换 v 份礼品 :param v: 目标礼品数目 :return: 能兑换返回True,不能返回False """ # 兑换v份礼品原始需求:x=少券总需求,y=多券总需求 x, y = a * v, b * v # 如果多券需求超过持有上限,调整兑换组合 if y >= m and b > a: t = (y - m + (b - a) - 1) // (b - a) y -= t * (b - a) x += t * (b - a) # 调整后两种券需求都不超过持有量则可行 return x <= n and y <= m # 二分查找最大可兑换份数 l, r = 0, int(1e9) while l < r: mid = (l + r + 1) // 2 if check(mid): l = mid else: r = mid - 1 print(r)
最大公因数



# 读取数字个数n、查询次数q n, q = map(int, input().split()) # 读取数组并升序排序 a = sorted(list(map(int, input().split()))) # 欧几里得算法求最大公约数 def gcd(a, b): if a == 0 or b == 0: return a + b return gcd(b, a % b) # 计算相邻元素差值的整体最大公约数 g = 0 for i in range(1, n): diff = a[i] - a[i - 1] g = gcd(g, diff) # 处理每组查询 for i in range(q): val = a[0] + i + 1 print(gcd(g, val))
平均分配
题目描述
小 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:]))



