第二阶段
第一关-统计分数的麻烦
“绿盟杯”比赛过后，赛事承办方的各位工作人员们就开始分头统计各个参赛队伍和同学的成绩了。赛事规模很大，有10000个队伍参加。经过工作人员认真负责的统计，本来已经统计好了这一万个队伍的分数和排名，并按照排名从高到低依次进行了编号（从1到10000）但是由于一个非常偶然的因素，导致其中三个编号的数据丢失，而且剩余编号的顺序也全被打乱了。
你需要编写一个程序，根据还保留的统计数据，来判断哪些编号的数据丢失了，并将这些编号按照从小到大的顺序重新拼接为一个新数字，然后计算这个新数字除以11的余数。如丢失了编号为41、17、25的数据，则最后你需要输出的结果是172541除以11的余数。
编程要求
补全右侧代码区中的get_lost_scores(self, scores)函数，找出丢失的三个编号并按指定格式输出一个新数字除以11的余数。函数参数说明如下：
scores 剩余的被打乱顺序的编号,一个字符串列表
测试说明
样例1：
输入：
除15、48、56外的其余9997个数组成的乱序数组
输出：
9
样例2：
输入：
除22、76、83外的其余9997个数组成的乱序数组
输出：
5
官方解答：考查了range()函数、集合set的减法、sorted()函数、
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class GetScores:
def get_lost_scores(self, scores):
N = sorted(set(range(1, 100001)) - set(int(x) for x in scores))
M = str(N[0]) + str(N[1]) + str(N[2])
print(int(M) % 11)
第二关-最强战队
绿盟和各大名企合作，举办编程能力大赛，需要选拔一支参赛队伍。队伍成员全部来自“绿盟杯”中表现优秀的同学，每个同学都根据在比赛中的表现被赋予了一个能力值。现在被召集的N个同学已经集结完毕，他们按照编号依次站成了一排。
你需要编写一个程序，从N个同学中选出S名同学，要求选出的同学的能力值的乘积最大，且要求被选出的相邻两个同学的编号的差不超过D。
编程要求
补全右侧代码区中的get_best_team(self, numbers, abilities, selectedNum, distance)函数，实现找出能力值乘积最大而且满足编号要求的同学并输出。函数参数说明如下：
numbers 召集到的同学的人数，整型
abilities 各个同学的能力值（依次对应不同编号的同学,整型列表，列表的index就是学生的编号）
selectedNum 需要选出的同学的人数，整型
distance 相邻同学的编号的差的最大值，整型
测试说明
样例1：
输入：
3 , [7,4,7] , 2 , 50
输出：
49
官方解答：考查动态规划
https://www.nowcoder.com/questionTerminal/661c49118ca241909add3a11c96408c8?commentTags=C%2FC%2B%2B
>>> [[1,2]*2 for i in range(3)]
[[1, 2, 1, 2], [1, 2, 1, 2], [1, 2, 1, 2]]
>>> (1 << 64) * -1
-18446744073709551616L
>>> (1 << 64)
18446744073709551616L
>>> (1 << 63)
9223372036854775808L
>>> (1 << 6)
64
>>> (1 << 4)
16
>>> (1 << 2)
4
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class BestTeam:
def get_best_team(self, numbers, abilities, selectedNum, distance):
dmax = [[0] * numbers for i in range(selectedNum)]
dmin = [[0] * numbers for i in range(selectedNum)]
res = (1 << 64) * -1 # 先令res为一个无穷小的数
for i in range(numbers): #
dmax[0][i] = dmin[0][i] = abilities[i]
for k in range(1, selectedNum):
for pre in range(max(0, i - distance), i):
dmax[k][i] = max(dmax[k][i],
max(dmax[k - 1][pre] * abilities[i], dmin[k - 1][pre] * abilities[i]))
dmin[k][i] = min(dmin[k][i], min(dmax[k - 1][pre] * abilities[i], dmin[k - 1][pre] * abilities[i]))
res = max(res, dmax[selectedNum - 1][i])
print(res)
第三关-完美的团建活动
“绿盟杯”决赛完美落幕之后，赛事团队组织去一个风景优美的山区进行团建。由于人数众多必须选择一块较大的场地。他们找到了一块足够大的地方，但是场地上却散布着许多石头，为了方便活动，必须把这些石头挪开。现在我们假设整个场地是一块矩形的地图，地图坐标的横纵坐标均为非负整数，每个坐标点上有一个值：
image.png
0：代表无法从这个点通过1：代表这个点可以顺利通过N(大于1)：代表这个点上有一个可以去除的石头，且石头的大小是N
</pre>
现在要求你按照以下规则移除石头：从当前位置出发，按石头的大小依次移除石头，每次先移除从当前位置出发能够达到的最小的石头，每移除一个石头，该石头所在坐标就可以通行即值变为1。你需要编写一个程序计算出从坐标（0,0）出发，移除所有石头需要走的最小步数，注意，石头是无法翻越的,而且如果（0,0）上有石头可以直接移除。如果无法移除所有的石头就输出-1。一个温馨的小提示仅供大家参考，大家注意哦：使用BFS算法再配以适合的数据结构如优先队列等是一个不错的选择！
编程要求
补全右侧代码区中的get_minium_steps(self, stones)函数，完成挑战任务中提出的要求，并将结果作为返回值返回：按照石头大小，从小到大依次移除场地中的石头，返回最小的步数，如果无法移除所有的石头就返回-1。
函数参数说明如下：
stones表示场地中各个坐标点的情况（List < List <int> >类型）
（List.get(0).get(0)代表坐标（0,0）），即0代表无法通过，1代表可以顺利通过，大于1的正数代表存在一个可以移除的石头，且石头的大小是该点的值。
测试说明
样例1：
输入：
1,2,3
0,0,4
7,6,5
输出：
6
样例2：
输入：
1,2,3
0,0,0
7,6,5
输出：
-1
官方解答：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class TeamBuilding:
def get_minium_steps(self, stones):
# Add sentinels (a border of zeros) so we don't need index-checks later on.
stones.append([0] * len(stones[0]))
for row in stones:
row.append(0)
# Find the trees.
trees = [(height, i, j)
for i, row in enumerate(stones)
for j, height in enumerate(row)
if height > 1]
# Can we reach every tree? If not, return -1 right away.
queue = [(0, 0)]
reached = set()
for i, j in queue:
if (i, j) not in reached and stones[i][j]:
reached.add((i, j))
queue += (i+1, j), (i-1, j), (i, j+1), (i, j-1)
if not all((i, j) in reached for (_, i, j) in trees):
return -1
# Distance from (i, j) to (I, J).
def distance(i, j, I, J):
now, soon = [(i, j)], []
expanded = set()
manhattan = abs(i - I) + abs(j - J)
detours = 0
while True:
if not now:
now, soon = soon, []
detours += 1
i, j = now.pop()
if (i, j) == (I, J):
return manhattan + 2 * detours
if (i, j) not in expanded:
expanded.add((i, j))
for i, j, closer in (i+1, j, i < I), (i-1, j, i > I), (i, j+1, j < J), (i, j-1, j > J):
if stones[i][j]:
(now if closer else soon).append((i, j))
# Sum the distances from one tree to the next (sorted by height).
trees.sort()
return sum(distance(i, j, I, J) for (_, i, j), (_, I, J) in zip([(0, 0, 0)] + trees, trees))
网友评论