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

2023-12-27 13:10:29

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

【六级编程题1】

【试题名称】:闯关游戏

时间限制2.0 s

内存限制128.0 MB

问题描述】

你来到了一个闯关游戏。

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

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

输入描述】

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

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

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

输出描述】

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

【数据规模】

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

对于40%的测试点,保证N20;保证M2

对于所有测试点,保证N10?;保证M100

【分析】

方法一

递推算法,从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名员工,编号从0N-1。其中,除了0号员工是老板,其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi

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

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

输入描述】

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

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

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

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

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

输出描述】

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

数据规模】

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

对于所有测试点,保证3≤N≤300Q≤100

【分析】

方法一

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

时间复杂度:O(QNM)≤O(QN2)100×30029×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×30029×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]])

【运行结果】

?

文章来源:https://blog.csdn.net/hz_zhangrl/article/details/135237822
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。