首页 > itarticle > 问题 d 数字转换

问题 d 数字转换

admin 12月 09, 2020 0

可以把这种转换关系看成一棵树，有关系的两个点连一条边，不难发现，实际上这是个森林。
但要求的是树的最长边，也就是直径，那么容易想到求一遍森林中所有的树的直径，取一个最大值，但是太麻烦了。
我们画个图不难发现，节点 1 一定在森林中最大的树中，所以只要以求以 1 为根节点的树的直径就是答案了

bfs版本


#include <iostream>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 50007
using namespace std;

int head[MAXN],ver[MAXN<<2],nxt[MAXN<<2],tot=0;
int n,root,maxdep,d[MAXN];
bool v[MAXN];
queue<int> q;

inline void (int x,int y){
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}

inline int sum(int x){
    int res=1;
    for(int i=2;i<=(int)(x/i);++i){
        if(x%i==0) res+=(i+(x/i));
        if(i*i==x) res-=i;
    }
    return res;
}

inline void bfs(int s){
    memset(v,0,sizeof(v));
    memset(d,0,sizeof(d));
    maxdep=0;
    v[s]=1;d[s]=1;
    q.push(s);
    while(q.size()>0){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(v[y]) continue;
            v[y]=1;
            d[y]=d[x]+1;
            if(d[y]>maxdep){maxdep=d[y];root=y;}
            q.push(y);
        }
    }
}

inline void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int y=sum(i);
        if(y<i){
            add(i,y),add(y,i);
        }
    }
    bfs(1);
    bfs(root);
    printf("%dn",maxdep-1);
}

int main(){
    init();
    return 0;
}

dp版本


#include <iostream>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 50007
using namespace std;

int head[MAXN],ver[MAXN<<2],nxt[MAXN<<2],tot=0;
int n,root,maxdep,d[MAXN];
bool v[MAXN];
queue<int> q;

inline void (int x,int y){
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}

inline int sum(int x){
    int res=1;
    for(int i=2;i<=(int)(x/i);++i){
        if(x%i==0) res+=(i+(x/i));
        if(i*i==x) res-=i;
    }
    return res;
}

inline void dp(int x){
    v[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(v[y]) continue;
        dp(y);
        maxdep=max(maxdep,d[x]+d[y]+1);
        d[x]=max(d[x],d[y]+1);
    }
}

inline void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int y=sum(i);
        if(y<i){
            add(i,y),add(y,i);
        }
    }
    dp(1);
    printf("%dn",maxdep);
}

int main(){
    init();
    return 0;
}