第一题：密码翻译
解题思路：字典
用字典这种hash表快速实现密码翻译。
dictionary = dict()for i in range(65, 90):dictionary[chr(i)] = chr(i+1)
dictionary[chr(90)] = chr(65)
for i in range(97, 122):dictionary[chr(i)] = chr(i+1)
dictionary[chr(122)] = chr(97)password = input()
new_password = ''
for each in password:if each in dictionary:new_password += dictionary[each]else:new_password += eachprint(new_password)第二题：寻宝
解题思路：最小生成树
本代码用最小生成树的Kruskal算法实现。
不了解此算法的可以参考网上大神的介绍：最小生成树介绍
N, M = [int(each) for each in input().split()]
graphic = []
for i in range(M):graphic.append([int(each) for each in input().split()])
graphic = sorted(graphic, key=lambda x: x[2])
trees = [{i} for i in range(1, N+1)]def same_tree(node1, node2):for each_tree in trees:if node1 in each_tree:if node2 in each_tree:return Trueelse:return Falsedef union_tree(node1, node2):new_tree = set()for each_tree in trees:if node1 in each_tree:new_tree.update(each_tree)tree1 = each_treeif node2 in each_tree:new_tree.update(each_tree)tree2 = each_treetrees.remove(tree1)trees.remove(tree2)trees.append(new_tree)for each_path in graphic:if same_tree(each_path[0], each_path[1]):continueelse:union_tree(each_path[0], each_path[1])if len(trees) == 1:print(each_path[2])break第三题：打车
'''
解题思路：贪心算法
1、在付钱时尽可能先用小面额的硬币，直至达到支付金额。
2、在取回多余的硬币时尽可能先取回大面额的硬币，直至再也不能取回硬币。
'''
n, s = [int(each) for each in input().split()]
p = [int(each) for each in input().split()]
p.sort(reverse=True)money = 0
coins = []
while money < s:coin = p.pop()money += coincoins.append(coin)
coins_number = len(coins)coins.reverse()
remove_number = 0
for each_coin in coins:if money - each_coin < s:continueelse:money -= each_coinremove_number += 1
print(coins_number - remove_number)第四题：美丽的项链
解题思路：动态规划
1、用1个(m+1)维的列表dp表示宝珠数量为t(0<=t<=m)时最多有几种满足条件的项链总数。
2、通过加入不同种类水晶不同数量的宝珠来更新dp。Ps.当未加入任何宝珠时，dp[0]=1，dp[1~m]=0，表示如果项链不需要任何宝珠，满足条件的项链有1种。
3、在代码中，用变量i表示水晶种类，变量x表示在项链中加入i种水晶的宝珠的数量，变量y更新加入i种水晶宝珠x颗时的dp，将更新的结果暂时保存在列表dp_中。
4、举例：加入i种水晶x颗后，dp_[y]=dp_[y]+dp[y-x]，即表示用目前满足条件的有y颗宝珠的项链总数与之前满足条件的有(y-x)颗宝珠的项链总数的和来更新满足条件的有y颗宝珠的项链总数。
n, m = [int(each) for each in input().split()]dp = [0] * (m + 1)
dp[0] = 1
for i in range(n):l, r = [int(each) for each in input().split()]dp_ = [0] * (m + 1)for x in range(l, r+1):for y in range(x, m+1):dp_[y] += dp[y-x]dp = dp_print(dp[m])第五题：排列
解题思路：任何一次交换都能确保两个位置都满足条件
如果index == p[index]，那么把p[index]和p[index+1]交换位置，交换后p[index]和p[index+1]都能满足条件。
考虑特殊情况：即p[n]=p[n]
n = int(input())
p = [int(each)-1 for each in input().split()]index = 0
count = 0
while index < n-1:if index == p[index]:p[index], p[index + 1] = p[index + 1], p[index]count += 1index += 2else:index += 1if index == n:print(count)
elif index == p[index]:print(count+1)
else:print(count)第六题：勇敢的妞妞
解题思路：动态规划
1、用1个n维的列表dp表示带有第i(0<=i<=n-1)件装备时，能够达到的最大增益。
2、最少带1件装备，所以dp的初始值就是各个装备单独携带时的增益。
3、可以携带的装备数量每增加1，就更新一次dp。
4、在每一次的更新中，都把当前的dp和新加入的装备比较，如果新加入的装备可以提高以后增益，则执行更新。
python执行效率低下，通过率50%，求高手提高代码的运行效率。
n, k = [int(each) for each in input().split()]
equipments = []
for i in range(n):equipments.append([int(each) for each in input().split()])dp = equipments[:]
for i in range(1, k):dp_ = dp[:]for x in range(n):for y in range(x+1, n):ability = dp[x][:]for abi in range(5):if ability[abi] < equipments[y][abi]:ability[abi] = equipments[y][abi]if sum(ability) > sum(dp_[x]):dp_[x] = abilitydp = dp_print(max([sum(each) for each in dp]))