从用户旅程角度做网站分析,做网站还是做淘宝,黄页网站大全免费网在线,加强文明网站建设参考#xff1a;20220903美团笔试题解_笔经面经_牛客网
前两个签到题就不整理了
第三题#xff1a;
给定一棵有n个节点的树#xff0c;节点用1,2,…n编号。1号节点为树的根节点#xff0c;每个节点上有一个用大写字母表示的标记。求每个
节点的子树中出现的字母标记种类…参考20220903美团笔试题解_笔经面经_牛客网
前两个签到题就不整理了
第三题
给定一棵有n个节点的树节点用1,2,…n编号。1号节点为树的根节点每个节点上有一个用大写字母表示的标记。求每个
节点的子树中出现的字母标记种类数。
注子树的定义设T是有根树a是T中的一个顶点由a以及a的所有后裔后代导出的子图称为有根树T的子树。
输入描述
第一行输入一个正整数n表示树的节点数量。
第二行输入n-1个正整数第i个整数表示第i1号节点的父亲节点。
第三行输入长度为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
解题报告
解法多样主要就是每个节点都记录一下子树出现过的字符。可以用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, start1):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) 第四题
有n个城市城市从1到n进行编号。小美最初住在k号城市中。
在接下来的m天里小美每天会收到一个任务她可以选择完成当天的任务或者放弃该任务。
第i天的任务需要在ci号城市完成如果她选择完成这个任务
若任务开始前她恰好在ci号城市则会获得ai的收益
若她不在c号城市她会前往c号城市获得bi的收益。
当天的任务她都会当天完成任务完成后她会留在该任务所在的ci号城市直到接受下一个任务。
如果她选择放弃任务她会停留原地且不会获得收益。
小美想知道如果她合理地完成任务最大能获得多少收益输入描述
第一行三个正整数nm和k表示城市数量总天数初始所在城市。
第二行为m个整数c1, c2...cm其中ci表示第i天的任务所在地点为ci
第三行为m个整数a1, a2...am其中ai表示完成第i天任务且地点不变的收益。
第四行为m个整数b1, b2...bm其中bi表示完成第i天的任务且地点改变的收益。
1k,cin3e4
1m3e4
0ai,bi1e9输出描述
输出一个整数表示小美合理完成任务能得到的最大收益。input:
3 5 1
2 1 2 3 2
9 6 2 1 7
1 3 0 5 2output:
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[i1]的方式。但是这种方式由于赋值号左边是不确定的因此较难优化因此我们用第一种方法去定义。
状态转移也比较显然
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]), v1elif v v2[0]:v2 (v, c[i])print(max(pre))
