数字转换

快来打我* 2021-11-05 09:18 304阅读 0赞

### 数字转换 ###

时间限制: 1 Sec 内存限制: 512 MB

题目描述

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

输入

输入一个正整数n。

输出

输出不断进行数字变换且不出现重复数字的最多变换步数。

样例输入

样例输出

提示

一种方案为4->3->1->7。  
对于100%的数据，1<=n<=50000。

这道题首先要求一下从一到n所有数的约数和，如果小于n的话就建边，然后求这棵树的直径就好了。

而树的直径可以用两遍dfs来找，第一遍找到离根节点最远的点，第二遍以离根节点最远的点为起点找离它最远的点，

则这个最远的距离即是直径。

下面是代码：

#include<bits/stdc++.h>
    using namespace std;
    int head[200010],to[200010],nxt[200010],tot = 1,n;
    int max_n,p,q,fa[200010],vis[200010],ans,sum,f[200010];
    void add(int x,int y) 
    {
        to[tot] = y;
        nxt[tot] = head[x];
        head[x] = tot++;
    }
    int ys(int x)
    {
    	int sum=0;
    	for(int i=1;i*i<=x;i++)
    	{
    		if(x%i==0) 
    		{
    			sum+=i,sum+=(x/i);
    			if(i*i==x) sum-=i;
    		}
    	}
    	sum-=x;
    	return sum;
    }
    void dfs1(int u,int fa_,int len) 
    {
        if(len>max_n) 
    	{
            max_n=len;
            p=u;
        }
        for (int i=head[u];i;i=nxt[i]) 
    	{
            int v=to[i];
            if(v==fa_) continue;
            dfs1(v,u,len+1);
        }
    }
    void dfs2(int u,int fa_,int len) 
    {
        if(len>max_n) 
    	{
            max_n=len;
            q=u;
        }
        fa[u]=fa_;
        for(int i=head[u];i;i=nxt[i]) 
    	{
            int v=to[i];
            if(v==fa_) continue;
            dfs2(v,u,len+1);
        }
    }
    
    int main() 
    {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{
    		int xx=ys(i);
    		if(xx>=i) continue;
    		add(i,xx);
    		add(xx,i);
    		
    	}
    	dfs1(1,0,0);
    	max_n=0;
    	dfs2(p,0,0);
    	printf("%d",max_n);
        return 0;
    }

转载于:https://www.cnblogs.com/chen-1/p/11320954.html