TitanZhang

分类

算法浅谈(1) 题解(48)

/ 注册

TA的专栏 47篇文章 1人订阅

2020牛客暑期多校训练营

47篇文章 1255人学习

全部文章（共5篇）

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

树形DP-虚树的思路&例题

虚树入门前置知识掌握求lca，dfs序，每个点的深度，两点之间的距离等操作什么是虚树虚树的核心思想，就是保留一棵树上有用的&关键的点，重新构建一棵“虚”树，更加快速地跑带关键点的树形dp。怎么用虚树这里就需要用到上面提到的求lca(最近公共祖先)技术。我们对一棵虚树的要求是，节点...

虚树树形dp

2020-08-01

1 748

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