夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
LOJ 10155 – 「一本通 5.2 例 3」数字转换

题面

传送门

如果一个数 $x$ 的约数和 $y$ (不包括他本身)比他本身小,那么 $x$ 可以变成 $y$ , $y$ 也可以变成 $x$ 。例如 $4$ 可以变为 $3$ , $1$ 可以变为 $7$ 。限定所有数字变换在不超过 $n$ 的正整数范围内进行,求不断进行数字变换且不出现重复数字的最多变换步数。

 

解题思路

这道题的标签是树形 DP,但有一种更简便的做法。

首先我们可以预处理出 1~n 之间的转换关系,然后连边,形成一张图。

例如 4 的因数和是 3,那么 4 和 3 可以相互转换,那么在它们之间连一条有向边。

预处理完以后,我们得到了一张图。这个问题被转化成了求这张图的最长链。

那么怎么求图上的最长链呢?

从图上的任意一个结点开始,找到离这个结点最远的结点。然后再从这个结点找出离它最远的结点,它们之间的距离就是最长链的长度。

很明显,用 dfs 就可以求出最长链的长度了。我们首先从 1 开始 dfs(因为不管 n 是多少,点 1 必然存在),找到离它最远的结点,然后再 dfs 一遍,找到最远的结点就是答案。

代码

暂无评论

发送评论 编辑评论


				
上一篇
下一篇