2023年12月GESP Python五级编程题真题解析

【五级编程题1】

【试题名称】：小杨的幸运数

【问题描述】

小杨认为，所有大于等于a的完全平方数都是他的超级幸运数。

小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数，小杨规定，可以将它一直+1，直到它变成一个幸运数。我们把这个过程叫做幸运化。例如，如果a=4，那么4是最小的幸运数，而1不是，但我们可以连续对1做3次+1操作，使其变为4，所以我们可以说，1幸运化后的结果是4。

现在，小样给出N个数，请你首先判断它们是不是幸运数；接着，对于非幸运数，请你将它们幸运化。

【输入描述】

第一行2个正整数a, N。

接下来 行，每行一个正整数 ，表示需要判断（幸运化）的数。

【输出描述】

输出N行，对于每个给定的x，如果它是幸运数，请输出“lucky”，否则请输出将其幸运化后的结果。

【数据规模】

对于30%的测试点，保证a,x≤100，N≤100。

对于60%的测试点，保证a,x≤10?。

对于所有测试点，保证a≤1,000,001；保证N≤2×10?；保证1≤x≤1,000,001。

【分析】

方法一

如x>=a，判是否是完全平方数或完全平方数的倍数，输出“lukey”。如 int(x?·?)= x?·? 则为完全平方数，在Python中x**0.5//1比int(x**0.5)快3倍左右；x不是完全平方数，则完全平方数的倍数个数不超过x?·?，如是整数倍数，则求商是否是完全平方数？

对小于a或不是完全平方数或倍数的，则需要加1至大于等于a，直到是完全平方数或完全平方数的倍数，输出该数。

搜索2个完全平方数的次数不超过2001(2001*2001-2000*2000)，找完全平方数倍数不超过x?·?

时间复杂度：O(n(x?·?+2001))，约2×10?×(1001+2001)≤6.1×10?，应该不会超时。

【完整代码】

a, n = [int(i) for i in input().split()]???????????????# 输入a和n
def p_square(n):???????????????????????????????????????# 判完全平方数或其倍数
??? if n**0.5 == n**0.5//1:
???? ???return True
??? else:
??????? for i in range(2,int(x**0.5)+1):?????????????? # 倍数不超过int(x**0.5)
??????????? if x // i == x / i and (x//i)**0.5 == (x//i)**0.5//1:
??????????????? return True
??????? else:
??????????? return False
for i in range(n):?????????????????????????????????????# 循环输入并处理n个数
??? x = int(input())???????????????????????????????????# 输入x
??? tf = False
??? if x >= a:
??????? if p_square(x):????????????????????????????????# 如果是完全平方数或其倍数
??????????? print('lucky')?????????????????????????????# 输出lucky 
??????????? tf = True
??? if not tf: ????????????????????????????????????????# 如果是则需要加1
??????? while True:
??????????? x += 1
??????????? if x >= a:
??????????????? if p_square(x):????????????????????????# 直到是完全平方数或其倍数
??????????????????? print(x)???????????????????????????# 输出该数
??????????????????? break

【运行结果】

方法二

先建完全平方数和其倍数表(简称lucky表)，将可能的数值范围内的完全平方数和其倍数纳入表中，如直接从表的x位置(索引)中找到的数=x，则输出“lucky”，否则输出该数。

因为题目给出a≤1,000,001，N≤2×10?，x≤1,000,001，所以最大的完全平方数不超过1001*1001，故先生成1001*1001+1元素为0的列表，在1~1001的平方大于等于a的位置填上平方数(lucky数)，并在其倍数位置填上相应倍数值(lucky数)。对于0值用后面与其最接近的lucky数填充。输了直接用x作为索引查询，如x作为索引的值是x，则a是lucky数，输出“lucky”，否则输出x作为索引的值。

时间复杂度：小于O(4x)，主要用于建表，1001×1001+1001×2001+2×10?<3.3×10?。

【完整代码】

a, n = [int(i) for i in input().split()]?? ??????# 输入a和n
max_ly = 1001 * 1001?????????????????????????????# 最大的lucky数不超过此数，x≤1000001
nr_ly = [0 for i in range(max_ly + 1)]???????????# 生成max_ly+1个元素为0的列表
for i in range(1, int(max_ly**0.5)+1):
??? if i*i >= a:???????????????????????????? ????# 大于等于a的完全平方数元素位置填入此数
??????? nr_ly[i*i] = i*i
??????? for j in range(i*i + i*i, max_ly, i*i):? # 其倍数元素位置也填入其倍数
??????????? nr_ly[j] = j
for i in range(max_ly, 0, -1):???????????????????# 两个lucky数之间最近的lucky数是后面的数
??? if not nr_ly[i]:?????????????????????????????# 如i是lucky数则有值，否则为0
??????? nr_ly[i] = nr_ly[i + 1]??????????????????# 0值则填入其后面的数(最接近的lucky数)
for i in range(n):???????????????????????????????# 输入n个x
??? x = int(input())???????????????????????????? # 输入x
??? if nr_ly[x] == x:????????????????????????????# 如果x是lucky数输出“lucky”
??????? print("lucky")
??? else:
??????? print(nr_ly[x])??????????????????????????# 否则输出最接近的lucky数(即x+1至lucky数)

【运行结果】

【五级编程题2】

【试题名称】：烹饪问题

【问题描述】

有N种食材，编号从0至N-1，其中第i种食材的美味度为ai。

不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为x和y，那么它们的契合度为x and y。

其中，and运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足 ，再逐位进行与运算。例如，12与6的二进制表示分别为1100和0110，将它们逐位进行与运算，得到0100，转换为十进制得到4，因此12 and 6 = 4。在 C++ 或 Python 中，可以直接使用 & 运算符表示与运算。

现在，请你找到契合度最高的两种食材，并输出它们的契合度。

【输入描述】

第一行一个整数N，表示食材的种数。

接下来一行N个用空格隔开的整数，依次为a0,…, aN-1，表示各种食材的美味度。

【输出描述】

输出一行一个整数，表示最高的契合度。

【数据规模】

对40%的测试点保证N≤1,000。

对所有测试点保证N≤10?，0≤ai≤2,147,483,647(231-1)。

【分析】

方法一

由于0≤ai≤2,147,483,647，所以(ai & aj)i≠j≥0，因此结果最大值的初值可定义为0。因为ai & aj = aj & ai，先取第1个与其它N-1个数进行按位与运算，如大于结果就赋给结果(求两数按位与的最大值)，再取第2个与其后N-2个数进行按位与运算，如大于结果就赋给结果(求两数按位与的最大值)，以此类推，直到所有数据都计算并比较大小。此解法时间复杂度为O(N2)，可以解决40%多的数据，当N≥10?就可能超时。

【完整代码】

n = int(input())??????????????????????????????????# 输入n
a = [int(i) for i in input().split()]?????????????# 输入n个食材的美味度
ans = 0???????????????????????????????????????????# 初值为0
for i in range(n-1):??????????????????????????????# 0≤i<n-1
??? for j in range(i+1,n):????????????????????????# i+1≤j<n
??????? if a[i] & a[j] > ans: ??????????????????? # a的下标为1~n-1
??????????? ans = a[i] & a[j]?????????????????    # ans为两种食材的美味度的最大值
print(ans)????????????????????????????????????????# 输出结果

【运行结果】

方法二

因为ai≤2,147,483,647(231-1)，最多31位二进制，从最高位开始枚举，时间复杂度O(31N)，可以解决所有数据，不超时。

【完整代码】

n = int(input())??????????????????????????????????????# 输入n
a = [int(i) for i in input().split()]???????????????? # 输入n个食材的美味度
ans = 0
for i in range(30,-1,-1):?????????????????????????????# 从最高位开始枚举
??? ans += 2**i?????? ????????????????????????????????# 加上当前二进制位为1
??? cnt = 0???????????????????????????????????????????# 统计数量
??? for j in range(n):????????????????????????????????# 遍历所有数
??????? if (ans & a[j] == ans):
??????????? cnt += 1
??? if cnt < 2:???????????????????????????????????????# 两个以下
??????? ans -= 2**i??????? ???????????????????????????# 这一位为0(原加1，现减去1)
print(ans) ???????????????????????????????????????????# 输出结果

【运行结果】