最新美团笔试题及解析（时间：2022年9月3号）
T1 乒乓球
乒乓球，被称为中国的“国球”，是一种世界流行的球类体育项目。一局比赛的获胜规则如下：
当一方赢得至少11分，并且超过对方2分及以上时，获得该局的胜利。
按照上述规则，小美和小团正在进行一局比赛，当前比赛尚未结束，此时小美的得分为a，小团的得分为b。小美想知道，在
最理想的情况下，她至少还要得多少分才可以赢下这场比赛。
输入描述
输入两个整数a、b。a表示当前小美获得的分数，b表示小团的分数。
0≤ a,b≤ 99.保证输入的比分合法，并且在该比分下比赛尚未结束。输出猫述
输出一个整数，表示小美至少还要得多少分才能获得这局比赛的胜利。input:
30 31output:
3签到题。
a, b = list(map(int, input().split()))
if a >= 11 and a - b > 2:print(0)
else:print(max(11, b + 2) - a)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 1output:
2 0 2 1首先求得原数组的mex值。删除一个数的时候，如果比这个mex值大，则不影响mex值，否则删除的数字为新的mex值。
n = int(input())
a = list(map(int, input().split()))
ans = []
s = set(a)
cnt = 0
for i in range(n + 2):if i not in s:cnt = ibreakprint(*[min(cnt,a[i]) for i in range(n)])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
ABCCADoutput:
4 3 1 2 1 1经典树遍历，因为只需要计算某个节点及其子树的出现的字母种类数，那么可以利用状态压缩的思想。假设你有一个26位的整数，某一位为0表示某个字母没出现过，某一位为1表明某字母出现过。比如10000000..0，表示只有一个A。
后序遍历即可，每次把子节点的结果汇聚到父节点。
n = int(input())
fa = list(map(int, input().split()))
s = input()
ans = [0] * n
g = [[] for _ in range(n)]
for i, c in enumerate(fa, start=1):g[c - 1].append(i)def solve(cnt):v = (1 << (ord(s[cnt]) - ord('A')))for nxt in g[cnt]: v |= solve(nxt)ans[cnt] = bin(v)[2:].count('1')return vsolve(0)
print(*ans)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 2output:
13先考虑一个自顶向下的dp，考虑函数f(i, k)，表示从第i个任务开始，当前所在位置为k可以得到的最大收益。不难写出，一共有3种情况：
- 不完成这个任务，直接选择f(i+1, k)
- 完成这个任务，且c[i]==k，那么此时贡献为f(i+1, k)+a[i]
- 完成这个任务，且c[i]!=k，那么此时贡献为f(i+1, c[i])+b[i]
选大的即可，可以写出如下代码：
n, m, k = list(map(int, input().split()))
c = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))@lru_cache(None)
def f(i, k):if i == m: return 0if c[i] == k: return f(i+1, k) + a[i]return max(f(i + 1, k),f(i + 1, c[i]) + b[i])
print(f(0, k))因为n和m都是3e4，上面这个代码复杂度显然无法全部通过。现在考虑优化：
假设现在位置为k，当前任务所在地为c[i]。c[i]==k很好考虑，直接加上即可。如果c[i]!=k呢？我们需要考虑的是从某一个非k的位置转移过来。
注意，c[i]!=k时，我们只需要找一个非k的位置转移过来即可，并不需要考虑从哪个位置过来。而且无论从哪个位置转移过来，假设是j位置，贡献都是 上一次到达j位置的最大贡献+b[i]。那么我们只需要找到最大的上一次到达j位置的最大贡献。
（插播一条广告：需要开通正版JetBrains全家桶的可以联系我，56元一年，正版授权，官网可查有效期，有需要的加我微信：poxiaozhiai6，备注：905。）
我们可以维护一个数组pre，pre[i]表示上次到达i位置可以获得的最大价值，利用这个数组，我们可以构造一版，假设当前位置为c[i]：pre[c[i]]=max(pre[c[i]], max{pre[j]+b[i] for j in range(1,n+1) if j!=c[i]} )
但是仍然不够，遍历pre仍然是一个n^2的过程，我们需要继续优化。可以发现，上面的pre[j]和i是无关的。我们每次转移的时候，只需要找到最大的pre[j]即可。但是如果单纯维护一个pre[j]，有可能j和c[i]是相等的，可能造成转移出问题。那么我们只需要维护2个最大的pre[j]，这样可以保证一定有一个值和c[i]不相等，最终达成一个时间复杂度O(n)的解法。
n, m, k = list(map(int, input().split()))
c = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))h = [(0, i) for i in range(1, n + 1)]
pre = [-1] * (n + 1)
pre[k] = 0
v1 = (0, k) # 最大
v2 = (0, 0) # 次大for i in range(m):v = 0# 直通if pre[c[i]] != -1:v = max(v, pre[c[i]] + a[i])if c[i] != v1[1]:v = max(v, v1[0] + b[i])elif c[i] != v2[1]:v = max(v, v2[0] + b[i])pre[c[i]] = max(pre[c[i]], v)if v > v1[0]:if c[i] == v1[1]:v1 = (v, c[i])else:v1, v2 = (v, c[i]), v1elif v > v2[0]:v2 = (v, c[i])print(max(pre))
