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

六、2023年12月GESP Python六级编程题

【六级编程题1】

【试题名称】：闯关游戏

时间限制：2.0 s

内存限制：128.0 MB

【问题描述】

你来到了一个闯关游戏。

这个游戏总共有N关，每关都有M个通道，你需要选择一个通道并通往后续关卡。其中，第i个通道可以让你前进ai关，也就是说，如果你现在在第x关，那么选择第i个通道后，你将直接来到第x+ai关（特别地，如果x+ai≥N，那么你就通关了）。此外，当你顺利离开第s关时，你还将获得bs分。

游戏开始时，你在第0关。请问，你通关时最多能获得多少总分？

【输入描述】

第一行两个整数M,N，分别表示关卡数量和每关的通道数量。

接下来一行M个用单个空格隔开的整数a0, a1,…,aM-1。保证1≤ai≤N。

接下来一行N个用单个空格隔开的整数b0, b1,…,bM-1。保证|bi|≤10?。

【输出描述】

一行一个整数，表示你通关时最多能够获得的分数。

【数据规模】

对于20%的测试点，保证M=1。

对于40%的测试点，保证N≤20；保证M≤2。

对于所有测试点，保证N≤10?；保证M≤100。

【分析】

方法一

用“递推”算法，从0关选择各通道，到所在关分数最大(避开0分、负分选通道)，每关再选择各通道的分值大于已有值则更新。

时间复杂度：O(NM)，10?×100≤10?，不会超时。

【完整代码】

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
dp = [0] * (n + 1)???????????????????????????????????# 到第i关获得的最高得分
for i in range(n):
??? for j in range(m):
??????? t = min(i + a[j], n)??????????????????????? ?# 最高通关数为第n关
??????? if dp[t] == 0:
??????????? dp[t] = dp[i] + b[i]
??????? else:
??????????? dp[t] = max(dp[t], dp[i] + b[i])?????????# 考虑有负值的情况，取大者
print(dp[n])

【运行结果】

方法二

0关通关为1分(b[0])，“遍历”各关，“遍历”各通道通关的上一关如有分数，则计算到本关的分数，取最大值(避开0分、负分选通道)。

时间复杂度：O(NM)，10?×100≤10?，不会超时。

【完整代码】

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
f = [b[0]]?????????????????????????????????????????????????# 添加第0关分
for i in range(1, n):
??? f.append(0)????????????????????????????????????????????# 本关初始0分
??? for pway in a:
??????? if i - pway >= 0 and f[i - pway]:????????????????? # 上一关存在并有分值
??????????? # 本站已有分值时，取本站与上一站分中大者，否则取上一站分
??????????? f[i] = max(f[i], f[i - pway]) if f[i] else f[i - pway]
??? if f[i]:???????????????????????????????????????????????# 本关通过加b[i]，负分不加
??????? f[i] += max(0, b[i])???????????????????????????????# 负分通道不走(避免进入负分关)
print(f[i])

【运行结果】

【六级编程题2】

【试题名称】：工作沟通

时间限制：2.0 s

内存限制：128.0 MB

【问题描述】

某公司有N名员工，编号从0至N-1。其中，除了0号员工是老板，其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。

该公司有严格的管理制度，每位员工只能受到本人或本人直接领导或间接领导的管理。具体来说，规定员工x可以管理员工y，当且仅当x=y，或x=fy，或x可以管理fy。特别地，0号员工老板只能自我管理，无法由其他任何员工管理。

现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？

【输入描述】

第一行一个整数N，表示员工的数量。

第二行N个用空格隔开的正整数，依次为f1,f2,…,fN-1。

第三行一个整数Q，表示共有Q场合作需要安排。

接下来Q行，每行描述一场合作：开头是一个整数m(2≤m≤N)，表示参与本次合作的员工数量；接着是m个整数，依次表示参与本次合作的员工编号(保证编号合法且不重复)。

保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。

【输出描述】

输出Q行，每行一个整数，依次为每场合作的主持人选。

【数据规模】

对于50%的测试点，保证N≤50。

对于所有测试点，保证3≤N≤300；Q≤100。

【分析】

方法一

先使用逐层向上(递归)的方式找到每个人的所有领导，标记在二维列表中，对于每个团队逐个查找最大编号的共同领导，即为答案。

时间复杂度：O(QNM)≤O(QN2)，100×3002≤9×10?≈10?，不会超时。

【完整代码】

n = int(input())
mngr = [[] for i in range(n)]?????????????????# 不能用[[]]*n
for k in [(i,int(j)) for i,j in enumerate(input().split())]:
??? mngr[k[1]].append(k[0]+1)
rel = [[0] * n for i in range(n)]?????????    # “行”为领导编号，“列”为员工编号
def dfs(row,col):
??? rel[row][col] = 1?????????????????????????# 存在领导关系则为1, 否则是0
??? for c in mngr[col]:
??????? dfs(row,c)
for i in range(n):????????????????????????????# 建每个人的所有领导关系(直接、间接)表
??? dfs(i,i)
q = int(input())
for _ in range(q):
??? x = [int(i) for i in input().split()][1:] # 第1个是人数本处用不上，丢弃
??? ans = -1
??? for r in range(n):
??????? for y in x:
??????????? if not rel[r][y]:?????????????????# 每位员工r都是领导，则不会break
??????????????? break
??????? else:
??????????? ans = r
??? print(ans)

【运行结果】

方法二

先使用逐级向上每个人的直接领导和间接领导，标记在二维列表中，对于每个团队逐个查找最大编号的共同领导，即为答案。

时间复杂度：O(QMN)≤O(QN2)，100×3002≤9×10?≈10?，不会超时。

【完整代码】

n = int(input())
b = [[0] * n for i in range(n)]
f = [0]+[int(i) for i in input().split()]?????????????# 直接领导关系
for i in range(n):????????????????????????????????????# 间接领导关系b[i][j]为1表示i是j的领导
??? b[i][i] = 1???????????????????????????????????????# 自己可以管自己
??? b[0][i] = 1???????????????????????????????????????# 老板管所有员工
??? sup = f[i]????????????????????????????????????????# 找直接领导
??? while sup:????????????????????????????????????????# 领导不是老板就继续找
??????? b[sup][i] = 1;
??????? sup = f[sup]??????????????????????????????????# 找间接领导(领导的领导)
q = int(input())
for _ in range(q):
??? a = [int(i) for i in input().split()]?????????????# 第1个a[0]是人数, 每次合作的员工列表
??? for i in range(2, a[0]+1):????????????????????????# 从第2个员工开始找与前面员工的共同领导
??????? for j in range(min(a[i], a[i - 1]), -1, -1):??# 从编号最小的开始
??????????? if b[j][a[i]] and b[j][a[i - 1]]:?????????# 如果是共同领导
??????????????? a[i] = j??????????????????????????????# 当前员工换成共同领导
??????????????? break???
print(a[a[0]])

【运行结果】

?