【20220903-美团笔试】

参考：20220903美团笔试题解_笔经面经_牛客网

前两个签到题就不整理了

第三题：

给定一棵有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

解题报告：

解法多样，主要就是每个节点都记录一下子树出现过的字符。可以用string，可以用二进制，可以用set，反正一共就26个字母

参考代码：

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)

---

第四题：

有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[i][j]代表第i天结束时小美在j号城市的最大收益。

其实可以有两种定义的方法；第i天结束时在j号城市，或者第i天开始时在j号城市（也就是第i-1天结束时在j号城市）。这两种方法各有好处，第一种的好处在于，可以直接if(c[i]==j),然后dp[i][]用dp[i-1][]转移过来，好处二是，因为题目给的就是初始所在城市，也就是dp[0][]当做初始化。如果用第二种方法，那最好是用dp[i]更新dp[i+1]的方式。但是这种方式由于赋值号左边是不确定的，因此较难优化，因此我们用第一种方法去定义。

状态转移也比较显然：

if c[i] == j:

        dp[i][j] = dp[i-1][j] + a[i] # 完成任务

else:

        t1 = dp[i-1][j] # 不完成任务

        t2= max(dp[i-1][1], dp[i-1][2], ...不包含dp[i-1][c[i]]..., dp[i-1][n]) + b[i] # 完成任务

        dp[i][j] = max(t1, t2)

不难发现，可以滚动数组优化一下，只用存下上一轮的最大值和次大值就可以了。（存两个值是为了保证有一个不是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))