美团笔试题及解析（时间：2022年9月3号）

逃离我推掉我的手 2023-09-27 08:23 20阅读 0赞

最新美团笔试题及解析（时间：2022年9月3号）

![f606b943c3824f79a6fd3e33124a0d10.png][]

## T1 乒乓球 ##

乒乓球，被称为中国的“国球”，是一种世界流行的球类体育项目。一局比赛的获胜规则如下：
    当一方赢得至少11分，并且超过对方2分及以上时，获得该局的胜利。
    按照上述规则，小美和小团正在进行一局比赛，当前比赛尚未结束，此时小美的得分为a，小团的得分为b。小美想知道，在
    最理想的情况下，她至少还要得多少分才可以赢下这场比赛。
    输入描述
    输入两个整数a、b。a表示当前小美获得的分数，b表示小团的分数。
    0≤ a,b≤ 99.保证输入的比分合法，并且在该比分下比赛尚未结束。
    
    输出猫述
    输出一个整数，表示小美至少还要得多少分才能获得这局比赛的胜利。
    
    input:
    30 31
    
    output:
    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 1
    
    output:
    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 = i
            break
    
    print(*[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
    ABCCAD
    
    output:
    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 v
    
    
    solve(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 2
    
    output:
    13

先考虑一个自顶向下的dp，考虑函数`f(i, k)`，表示从第i个任务开始，当前所在位置为k可以得到的最大收益。不难写出，一共有3种情况：

1.  不完成这个任务，直接选择f(i+1, k)
2.  完成这个任务，且c\[i\]==k，那么此时贡献为f(i+1, k)+a\[i\]
3.  完成这个任务，且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 0
        if 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]), v1
        elif v > v2[0]:
            v2 = (v, c[i])
    
    print(max(pre))

## 最后，点个赞吧，谢谢~ ##

[f606b943c3824f79a6fd3e33124a0d10.png]: https://img-blog.csdnimg.cn/f606b943c3824f79a6fd3e33124a0d10.png