TitanZhang

题解

算法浅谈(1)

/ 注册

全部文章 / 题解（共4篇）

2020牛客暑期多校训练营（第九场） B Groundhog and Apple Tree 来自专栏

题目大意有一个n个点的树，走过每一条边时会减少一定的hp，每条边只能最多经过2次（即每个子树只能进出一次）。吃了第i个点的苹果会回复a[i]的hp。可以在原地休息，每个单位时间回复1hp。hp不能为负。从根节点1开始出发，初始hp为0，要求经过所有点后返回1号点，求最少休息时间。解题思路这道题...

贪心树形dp

2020-08-09

2 776

2020牛客暑期多校训练营（第九场）K-The Flee Plan of Groundhog 来自专栏

题目大意给定一棵有n个节点，n-1条边的树，每条边长度为1，开始土拨鼠在1号节点，沿着最短路走向n号。土拨鼠出发t秒钟后，Orange以2m/s的速度跑向土拨鼠，而土拨鼠以1m/s的速度向任意方向逃跑。设每秒钟土拨鼠先移动Orange再移动。土拨鼠可以选择留在原地。求Orange最晚几秒钟能...

树形dp

2020-08-08

5 794

2020牛客暑期多校训练营（第一场）B-Infinite Tree 来自专栏

题目大意定义为n的最小质因子，构造一棵无限的树，树上每个n(n>1)与相连。定义为到间的边的数量（距离），给出与数组，求出。解题思路一本题因为树上节点过多，用虚树来优化树形dp是一种方法。所以，我们可以虚树二次扫描换根，求解树的带权重心来得到答案。带权重心介绍：https://b...

虚树树形DP 换根

2020-07-30

1 975

2020牛客暑期多校训练营（第三场）J Operating on the Tree 来自专栏

题目大意这道题从G题（Operating on a Graph ）延伸而来，附上G题大意：给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色，于是所有和 oi 相邻的...

树形dp 组合数学

2020-07-23

1 791