携程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