2023-03-29 22:21 已编辑 广州城市职业学院 Java
关注
携程0329开发笔试题解
投票
T1 计算圆圈个数 直接计数即可
T2 排列构造，需要K个好元素。只需要选择0, 2, 4,..., 2*(k-1)下标的地方依次填入n-k+1, n-k+2, ... ,n，也就是倒数k大的数，剩下的地方把剩下的地方填写即可
T3 x的阶乘范围决定了x不会超过15，枚举x，然后y取n/x和(n/x)+1计算哪个绝对值小即可。注意x和y不能取2，但可能取1。提交时感觉有个样例bug，x取1时按理说y直接消了取多少都可以，但是取n不通过，取1就通过了。
T4 树形DP，直接DFS，计算孩子允许染色和不允许染色的情况，返回两个状态：一个是不允许自己和孩子之间染色，一个是允许，两种情况下的权值。核心参考代码如下：
def dfs(node):
draw, nodraw, drawed = [], [], [] # 存储孩子状态
for nei, W in G[node]:
if not flag[nei]:
flag[nei] = True
neiNoDraw, neiDraw = dfs(nei)
nodraw.append(neiNoDraw)
draw.append(neiDraw)
drawed.append(W + neiNoDraw)
if draw: # 如果不是叶子
noDrawAns = sum(map(max, zip(draw, nodraw)))
drawDiff = [drawed[i] - draw[i] for i in range(len(draw))]
maxDiffIndex = drawDiff.index(max(drawDiff))
drawAns = max(noDrawAns, drawed[maxDiffIndex]+sum(draw)-draw[maxDiffIndex])
return noDrawAns, drawAns
return 0, 0
T2 排列构造，需要K个好元素。只需要选择0, 2, 4,..., 2*(k-1)下标的地方依次填入n-k+1, n-k+2, ... ,n，也就是倒数k大的数，剩下的地方把剩下的地方填写即可
T3 x的阶乘范围决定了x不会超过15，枚举x，然后y取n/x和(n/x)+1计算哪个绝对值小即可。注意x和y不能取2，但可能取1。提交时感觉有个样例bug，x取1时按理说y直接消了取多少都可以，但是取n不通过，取1就通过了。
T4 树形DP，直接DFS，计算孩子允许染色和不允许染色的情况，返回两个状态：一个是不允许自己和孩子之间染色，一个是允许，两种情况下的权值。核心参考代码如下：
def dfs(node):
draw, nodraw, drawed = [], [], [] # 存储孩子状态
for nei, W in G[node]:
if not flag[nei]:
flag[nei] = True
neiNoDraw, neiDraw = dfs(nei)
nodraw.append(neiNoDraw)
draw.append(neiDraw)
drawed.append(W + neiNoDraw)
if draw: # 如果不是叶子
noDrawAns = sum(map(max, zip(draw, nodraw)))
drawDiff = [drawed[i] - draw[i] for i in range(len(draw))]
maxDiffIndex = drawDiff.index(max(drawDiff))
drawAns = max(noDrawAns, drawed[maxDiffIndex]+sum(draw)-draw[maxDiffIndex])
return noDrawAns, drawAns
return 0, 0
全部评论
LongLive13
门头沟学院 Java
有霉粉啊
TaylorSwift13 楼主
楼主 广州城市职业学院 Java
补充下细节：
T3 X枚举，然后Y直接取n/X和(n/X)+1计算哪个绝对值小即可；
T4 允许自己和孩子之间染色这个状态即drawAns的计算需要注意一下，应该选择与哪一个孩子染色呢？应当对每一个孩子考虑，“选择与它染色得到的最大权值”和“不选择与它染色”得到的最大权值之差，即代码中的drawDiff，这个差最大的就是染色对权值贡献最大的孩子，我们选择与它染色。
See_UAG
东北大学 Java
a了前两个，第三个一直是61.1，最后一个直接放弃
牛客278143450号
门头沟学院 Java
大佬太强了
相关推荐
查看12道真题和解析 03-29 21:22
Université Joseph Fourier-Grenoble 1 算法工程师 点赞 评论 收藏
分享