LOJ 10155 – 「一本通 5.2 例 3」数字转换

前言

从现在开始,这个博客要写一些题解了。起初,开这个博客只是好玩一样,没事就写写CSS、JS,然后把博客前端搞成了现在这个样子。以前博客只是偶尔记录一些东西,刷题也从来不记录,最近受一些学长的影响,突然觉得写解题报告也很有意思,以后基本上做的题,除了太水的,都会在这上面更新。

一直很想买一个域名,然后用博客框架搭一个自己的博客,以前用 WordPress 和 Hexo 都搭过博客,但是域名续费、虚拟主机(虽然可以用 Hexo+GithubPage/CodingPage 搭静态博客,但更新不方便,也没法随时更新,例如在机房,所以还是需要 WordPress 等框架)的花费和阅读量比太小,没必要去搭,也试过用免费的虚拟主机(000webhost),免费的域名(.tk .cf 等),但毕竟免费,速度慢,网页有水印(虽然屏蔽了),域名国内搜索引擎还不予收录,所以就丢弃了。目前会用这个博客园的博客,而且可能会用下去(其实现在阅读体验和私有博客也没什么大的区别了)。真香,Wordpress 真好用,虚拟主机和域名也不贵。

说了这么多,进入正题吧。

题面

传送门

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

 

解题思路

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

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

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

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

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

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

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

代码

暂无评论

发送评论


				
上一篇
下一篇