GESP-Python五级 题库
Python的内置函数 sorted() 可以对支持 for-in 循环的 str 、 list 、 tuple 、 dict 、 set 排序,且是稳定排序。
试题名称:数字选取
时间限制: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))
武器强化
时间限制:2.0 s
内存限制:512.0 MB
题面描述
小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第pi种武器,小杨可以花费ci金币将该材料对应的适配武器修改为任意武器。
小杨最喜欢第 1 种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你帮小杨计算为了满足该条件最少需要花费多少金币。
输入格式
第一行包含两个正整数n,m,含义如题面所示。
之后 m 行,每行包含两个正整数pi,ci,代表第 i 种强化材料的适配武器和修改花费。
输出格式
输出一个整数,代表能够使适配第 1 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。
输入样例
输出样例
样例解释
花费 1,将第三种强化材料的适配武器由 3 改为 1。此时,武器 1 有 2 种强化材料适配,武器 2 和武器 3 都各有 1 种强化材料适配。满足适配第 1 种武器的强化材料种类数严格大于其他的武器。

对于全部数据,保证有1≤n,m≤1000,1≤pi≤n,1≤ci≤109。
def calc(aim, n, cnt, cs): cur_cnt = cnt[0] res = 0 tmp = [] for i in range(1, n): buy = max(len(cs[i]) - aim + 1, 0) for j in range(buy): res += cs[i][j] cur_cnt += buy for j in range(buy, len(cs[i])): tmp.append(cs[i][j]) tmp.sort() for i in range(aim - cur_cnt): res += tmp[i] return res n, m = map(int, input().split()) cnt = [0] * n cs = [[] for _ in range(n)] for _ in range(m): p, c = map(int, input().split()) cnt[p - 1] += 1 cs[p - 1].append(c) for i in range(n): cs[i].sort() ans = 1000000000000000000 for i in range(max(cnt[0], 1), m + 1): ans = min(ans, calc(i, n, cnt, cs)) print(ans)
小杨的武器
时间限制: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 = 100010 a = [0] * N c = [0] * N n, m = map(int, input().split()) mx = -10000 s = input().split() for i in range(1, n + 1): c[i] = int(s[i-1]) mx = max(mx, c[i]) s = input().split() for i in range(1, m + 1): a[i] = int(s[i-1]) for i in range(1, m + 1): if n == 1 or a[i] > 0: mx += a[i] print(mx)
我们想让武器熟练度最大值尽可能大,所以我们可以贪心考虑把原本的最大值,加上所有的正的熟练度,这样他就会变得最大。
流程:读入n和m,然后读入一个字符串,这个字符串就是c的信息,我们转成int类型,并找出其中的最大值mx,然后再读入一个字符串,这个字符串就是a的信息,我们把这个字符串转成int类型,判断a数组,如果当前熟练度增加值为正数,则累加到最大值mx上。
特别的,如果n==1,也就是只有一个武器,所以每次只能用这一个,这种情况下即使是负数,也要累加上。
黑白格
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。
小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。
输入格式
第一行包含三个正整数n,m,k,含义如题面所示。
之后n行,每行一个长度为m的01串,代表网格图第i行格子的颜色,如果为0,则对应格子为白色,否则为黑色。
输出格式
输出一个整数,代表至少包含k个黑色格子的最小子矩形包含格子的数量,如果不存在则输出0。
输入样例
输出样例
样例解释
对于样例1,假设 (i,j) 代表第i行第j列,至少包含5个黑色格子的最小子矩形的四个顶点为 (2,4),(2,5),(4,4),(4,5),共包含6个格子。
数据范围

对于全部数据,保证有 1 ≤ n , m ≤ 100 , 1 ≤ k ≤ n × m
N = 110 w = [[0] * N for _ in range(N)] sum_w = [[0] * N for _ in range(N)] def main(): n, m, k = map(int, input().split()) for i in range(1, n+1): s = input() for j in range(1, m+1): w[i][j] = int(s[j-1]) sum_w[i][j] = sum_w[i][j-1] + w[i][j] ans = 0 for i in range(1, m+1): for j in range(i, m+1): num = [] now = 0 for l in range(1, n+1): tmp = sum_w[l][j] - sum_w[l][i-1] now += tmp num.append(now) if now >= k: if ans == 0: ans = (j-i+1) * l else: ans = min(ans, (j-i+1) * l) L, R = 1, l while L < R: mid = (L + R + 1) // 2 if now - num[mid-1] >= k: L = mid else: R = mid - 1 if now - num[L-1] >= k: if ans == 0: ans = (j-i+1) * (l-L) else: ans = min(ans, (j-i+1) * (l-L)) print(ans) if __name__ == "__main__": main()
1.二维数组存储对应格子颜色的值
2.使用前缀和的技巧来快速计算任意子矩形内的格子数量。这样一来,不需要重复遍历每个可能的子矩形来计算其中的黑色格子数,从而节省时间
3.通过检查每个可能的子矩形,计算其中的黑色格子数量。找到一个最小的子矩形,使得其中至少有k个黑色格子。
4.使用二分查找的技巧,在内部循环中快速定位满足条件的子矩形大小
5.最后,我们输出这个最小子矩形的面积。如果不存在满足条件的子矩形,则输出0
小杨的幸运数字
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨认为他的幸运数字应该恰好有两种不同的质因子,例如,12=2×2×3 的质因子有2,3,恰好为两种不同的质因子,因此12是幸运数字,而30=2×3×5 的质因子有2,3,5,不符合要求,不为幸运数字。
小杨现在有n个正整数,他想知道每个正整数是否是他的幸运数字。
输入格式
第一行包含一个正整数n,代表正整数个数。
之后n行,每行一个正整数。
输出格式
输出n行,对于每个正整数,如果是幸运数字,输出1,否则输出0。
输入样例
输出样例
样例解释
7的质因子有7,只有一种。
12的质因子有2,3 ,恰好有两种。
30的质因子有2,3,5,有三种。
数据范围

对于全部数据,保证有1≤n≤104,每个正整数ai满足 2≤ai≤106。
N = 10**5 + 10
a = [0] * N
def calc(x):
i = 2
mp = {}
while i * i <= x:
if x % i == 0:
mp[i]=1
while x % i == 0:
x //= i
i += 1
if x != 1:
mp[x]=1
return int(len(mp.items()))
def main():
n = int(input())
for i in range(1, n + 1):
a[i] = int(input())
x = calc(a[i])
if x == 2:
print("1")
else:
print("0")
if __name__ == "__main__":
main()1.计算输入数据的质因子的个数。具体实现中,可以从最小的质数开始试除,统计不重复的质因子个数。
2.当质因子个数为2时,返回1表示是幸运数字,否则返回0。
成绩排序
问题描述
有N名同学,每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序:
1. 比较总分,高者靠前;
2. 如果总分相同,则比较语文和数学两科总分,高者靠前;
3. 如果仍相同,则比较语文和数学两科的最高分,高者靠前;
4. 如果仍相同,则二人并列。
你需要输出每位同学的排名,如遇x人并列,则他们排名相同,并留空后面的x-1个名次。例如,有3名同学并列第1,则后一名同学自动成为第4名。
输入描述
第一行一个整数N,表示同学的人数。
接下来N行,每行三个非负整数ci,mi,ei分别表示该名同学的语文、数学、英语成绩。
保证0≤ci,mi,ei≤150。
输出描述
输出N行,按输入同学的顺序,输出他们的排名。
注意:请不要按排名输出同学的序号,而是按同学的顺序输出他们各自的排名
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入
样例输出
数据规模
对于30的测试点,保证N≤100,且所有同学的总分各不相同。
对于所有测试点,保证2≤N≤104。
N = int(input()) students = [] for i in range(N): c, m, e = list(map(int, input().split())) students.append((c + m + e, c + m, max(c, m), i)) students.sort(reverse = True) rank = [None for i in range(N)] last_student = None for i, student in enumerate(students): if student[:-1] != last_student: last_student = student[:-1] curr_rank = i + 1 rank[student[-1]] = curr_rank for r in rank: print(r)
B-smooth数(python)
题面描述
小杨同学想寻找一种名为B-smooth数的正整数。
如果一个正整数的最大质因子不超过B,则该正整数为B-smooth数。
小杨同学想知道,对于给定的n和B,有多少个不超过n的B-smooth数。
输入格式
第一行包含两个正整数n,B,含义如题面所示。
输出格式
输出一个非负整数,表示不超过n的B-smooth数的数量。
样例输入
样例输出
样例解释
在不超过10的正整数中,3-smooth 数有{1,2,3,4,6,8,9},共7个。
数据范围

对于全部数据,保证有1≤n≤106,1≤B≤106。
n, B = map(int, input().split()) is_prime = [True] * (n + 1) primes = [] max_prime_factor = [0] * (n + 1) for i in range(2, n + 1): if is_prime[i]: primes.append(i) max_prime_factor[i] = i for p in primes: if i * p > n: break is_prime[i * p] = False max_prime_factor[i * p] = max(max_prime_factor[i], p) if i % p == 0: break cnt = 0 for i in range(1, n + 1): if max_prime_factor[i] <= B: cnt += 1 print(cnt)
巧夺大奖
时间限制:1.0 s
内存限制:128.0 MB
问题描述
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则:
1、游戏分为n个时间段,参加者每个时间段可以选择一个小游戏。
2、游戏中共有n个小游戏可供选择。
3、每个小游戏有规定的时限和奖励。对于第i个小游戏,参加者必须在第Ti个时间段结束前完成才能得到奖励Ri。
小明发现,这些小游戏都很简单,不管选择哪个小游戏,他都能在一个时间段内完成。关键问题在于,如何安排每个时间段分别选择哪个小游戏,才能使得总奖励最高?
输入描述
输入第一行,包含一个正整数n。 既是游戏时间段的个数,也是小游戏的个数。约定1≤n≤500。
输入第二行,包含n个正整数。第i个正整数为Ti,即第i个小游戏的完成期限。约定1≤Ti≤n。
输入第三行,包含n个正整数。第i个正整数为Ri,即第i个小游戏的完成奖励。约定1≤Ri≤1000。
输出描述
输出一行,包含一个正整数C,为最高可获得的奖励。
样例输入1
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
样例输出1
230
样例解释1
7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏,其中第4、2、3、1、7个小游戏在期限内完成。因此,可以获得总计40+60+50+70+10=230的奖励。
total_segements = int(input())
limits = []
rewards = []
s_limits = input()
s_limits = s_limits.split(' ')
s_rewards = input()
s_rewards = s_rewards.split(" ")
for item in s_limits:
limits.append(int(item))
for item in s_rewards:
rewards.append(int(item))
games = []
for i in range(len(s_limits)):
# 结束时间,奖励值,是否可以选,是否选过
games.append([limits[i], rewards[i], False, False])
def check_chooseable(states, current):
for item in states:
if item[0] >= current:
item[2] = True
def get_current_max(states, current):
maximum = 0
chosen = None
for i in range(len(states)):
if states[i][2] and not states[i][3]:
if maximum < states[i][1]:
#print(states[i][1])
maximum = max(states[i][1], maximum)
chosen = i
if chosen is not None:
states[chosen][3] = True
return maximum
total = 0
#print(games)
for t in range(total_segements, 0, -1):
#print(t)
check_chooseable(games, t)
total += get_current_max(games, t)
#print(games)
print(total)

