真题磨练-20220903美团笔试算法反思学习（持续更新中）

本文参考：

王悟空的题解

看到别人的题解多喜欢用Python来写，这也是我使用Python的一次大胆尝试。对Python不熟悉的话，可以查阅我的另一篇文章算法学习-以刷题为导向的Python知识。

T1.乒乓球

乒乓球，被称为中国的“国球”，是一种世界流行的球类体育项目。一局比赛的获胜规则如下：
当一方赢得至少11分，并且超过对方2分及以上时，获得该局的胜利。
按照上述规则，小美和小团正在进行一局比赛，当前比赛尚未结束，此时小美的得分为a，小团的得分为b。小美想知道，在最理想的情况下，她至少还要得多少分才可以赢下这场比赛。

输入描述
输入两个整数a、b。a表示当前小美获得的分数，b表示小团的分数。
0≤ a,b≤ 99.保证输入的比分合法，并且在该比分下比赛尚未结束。
 
输出猫述
输出一个整数，表示小美至少还要得多少分才能获得这局比赛的胜利。
 
input:
30 31
 
output:
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

根据题意模拟就好：

a,b=map(int,input().split())
res = 0
if a >= 11 and a-b>=2:
    print(0)
else:
    print(max(11,b+2)-a)
1
2
3
4
5
6

T2.mex

若S表示一个非负整数集合，mex(S)的值为不属于集合S的最小非负整数。例如，mex({0,1,4})=2，mex({1，2})=0。
有n个互不相同的非负整数a1，a2，…an构成了一个非负整数集合A。小美想知道若将a；(1≤i≤n)从集合A中删除，剩下的n-1个数构成的新集合A'的mex值为多少？请输出i从1到n所有取值下新集合的mex值。

输入描述
第一行输入一个整数n，表示集合A的大小。
第二行输入n个整数a1，a2,…an。
n<5e4,ai≤1e9，保证ai互不相同。数字间两两有空格隔开。

输出描述
输出n个整数，相邻两个数之间用空格隔开。其中第i个数表示从集合A中删除aj，剩下n-1个数构成的新集合的mex值。

input:
4
5 0 3 1

output:
2 0 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

先找出原集合中的最小值minV，若删除的数小于该最小值minV，则输出删除的数，否则输出minV. 其中找最小值的逻辑可以学习下，用一个集合s接住输入的整数，然后在整数0-n中，一定能找到最小值。

n = int(input())
a = list(map(int,input().split()))
s = set(a)
minV = 0
for i in range(n+1):
    if i not in s:
        minV = i
        break

print(*[min(minV,a[i]) for i in range(n)])
1
2
3
4
5
6
7
8
9
10

T3.字母树

给定一棵有n个节点的树，节点用1,2,…n编号。1号节点为树的根节点，每个节点上有一个用大写字母表示的标记。求每个
节点的子树中出现的字母标记种类数。
注：子树的定义：设T是有根树，a是T中的一个顶点，由a以及a的所有后裔（后代）导出的子图称为有根树T的子树。
输入描述
第一行输入一个正整数n，表示树的节点数量。
第二行输入n-1个正整数，第i个整数表示第i+1号节点的父亲节点。
第三行输入长度为n的由大写字母组成的字符串s1s2s3...sn，第i个字符si表示第i号节点的标记。
3≤n≤50000.
数据保证形成一棵合法的树，字符串由大写字母组成。
输出描述
输出n个整数，相邻两个数之间用空格隔开，第i个整数表示第i号节点的子树中出现不同的字母种类数。

input:
6 
1 2 2 1 4
ABCCAD

output:
4 3 1 2 1 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

后序遍历DFS+全局数组ans记录，要计算每个节点及其子树出现的字母种类数，无关种类数量，其实就可以用位表示来记录每个节点出现的字母种类，假设每个节点有一个26位的整数，某一位为0表示某个字母没出现过，某一位为1表明某字母出现过。比如10000000…0，表示只有一个A。

首先要将输入转换为图的形式存储起来（一个节点及其后续节点的对应关系），答案通过全局变量记录每个节点的状态，采用后序遍历的方式，用v先保存根的字母种类，然后将子树的状态更新到根节点root上面，处理结果在左右递归以后，最后判断root节点用位表示的状态，记录到全局变量中，同时递归函数返回该节点的字母种类状态位表示。这里我们可以在构造的图中，将合法的点都遍历完直接退出，没有null这样的base情况需要判断。

n = int(input())
nodelist = list(map(int,input().split()))
s = input()
ans=[0]*n
# 存树，节点序号从0开始，存储每个节点的子节点
g =[[]for _ in range(n)]
for i,v in enumerate(nodelist,start=1):
    # 给的序号从1开始，第i个整数值表示第i+1号节点（从0开始为i号）的父亲节点
    g[v-1].append(i)
    
# 以当前node节点为根的子树的字母种类数
def dfs(node):
	# 后序遍历，遍历下来先用到了v
    v = (1<<(ord(s[node])-ord('A')))
    for nxt in g[node]:
        v |= dfs(nxt)
    # 递归后处理结果
    ans[node] = bin(v)[2:].count('1')
    return v
dfs(0)
print(*ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

T4.任务

有n个城市，城市从1到n进行编号。小美最初住在k号城市中。在接下来的m天里，小美每天会收到一个任务，她可以选择完
成当天的任务或者放弃该任务。第i天的任务需要在ci号城市完成，如果她选择完成这个任务，若任务开始前她恰好在ci号城
市，则会获得ai的收益；若她不在c号城市，她会前往c号城市，获得bi的收益。当天的任务她都会当天完成，任务完成后，
她会留在该任务所在的ci号城市直到接受下一个任务。如果她选择放弃任务，她会停留原地，且不会获得收益。小美想知道，
如果她合理地完成任务，最大能获得多少收益？

输入描述
第一行三个正整数n，m和k，表示城市数量，总天数，初始所在城市。
第二行为m个整数c1, c2...cm，其中ci表示第i天的任务所在地点为ci
第三行为m个整数a1, a2...am，其中ai表示完成第i天任务且地点不变的收益。
第四行为m个整数b1, b2...bm，其中bi表示完成第i天的任务且地点改变的收益。
1<=k,ci<=n<=3e4
1<=m<=3e4
0<=ai,bi<=1e9

输出描述
输出一个整数，表示小美合理完成任务能得到的最大收益。

input:
3 5 1
2 1 2 3 2
9 6 2 1 7
1 3 0 5 2

output:
13
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

看别人的题解是用动态规划做的，但是我对于其理解并不算特别深刻，因此先贴出别人的题解->王悟空的题解.