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