首页 > 代码库 > {CSDN}{英雄会}{砍树、石子游戏}

{CSDN}{英雄会}{砍树、石子游戏}

砍树

思路:

可以将题目意图转化为:给定一棵树,求其中最接近总权值一半的子树。

DFS求每个节点的所有子节点的权值和,遍历每个节点,最接近总权值一半的即为答案。复杂度O(N)。

 

石子游戏:

思路:

一个Nim博弈问题,寻找一个局面的平衡状态,由于是多堆石子,参看Nim博弈的相关理论。