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 一遍,找到最远的结点就是答案。

代码

#include<bits/stdc++.h>
using namespace std;
long long last[200005],to[200005],nextt[200005],v[200005],top=0,d[200005];
long long maxx=0,ans=0;
void add(int a,int b){//前向星 
    nextt[++top]=last[a];
    to[top]=b;
    last[a]=top;
}
int n;
void dfs(int x,int t){
	v[x]=1;
	if (t>maxx){//如果当前的距离大于已知最长距离,那么更新距离并记录当前结点 
		maxx=t;
		ans=x;
	}
	for (int i=last[x];i;i=nextt[i]){//搜索与当前结点有联系的结点 
		if (!v[to[i]]){
			dfs(to[i],t+1);
		}
	}
}
int main(){
	cin>>n;
	for (int i=2;i<=n;i++){//预处理 
		int tmp=1;
		for (int j=2;j<=sqrt(i);j++){
			if (i==j){
				break;
			}
			if (i%j==0){
				tmp+=j+i/j;
			}
		}
		if ((int)sqrt(i)*(int)sqrt(i)==i){
			tmp-=sqrt(i);
		}
		if (tmp>=i){//如果约数和大于等于其本身,那么跳过 
			continue;
		}
		add(i,tmp);
		add(tmp,i);
	}
	dfs(1,0);
	maxx=0;
	memset(v,0,sizeof(v));
	dfs(ans,0);
	cout<<maxx;
}

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇
下一篇