#10155. 「一本通 5.2 例 3」数字转换

2019-01-30 15:44:25


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

题意

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

思路

求树的最长链

设 $d1[i]$ 为以 $i$ 为根的子树中,i到叶子节点距离最大值

设 $d2[i]$ 为以 $i$ 为根的子树中,i的叶子节点距离次大值(除了最大值所在的子树)

若j为i的儿子,那么:

  • 若 $d1[j]+dis[i][j]>d1[i]$ ,则 $d2[i]=d1[i];d1[i]=d2[j]=dis[i][j];$
  • 否则,若 $d1[j]+dis[i][j]>d2[i]$ ,则 $d2[i]=d1[j]+dis[i][j]; $

最后扫描所有节点,最长链=max{d1[i]+d2[i]}

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long 
#define eps 1e-4
using namespace std;
//priority_queue<int,vector<int>,greater<int> > q1;
//priority_queue<int> q2;
//set<int> s;
//list<int> l;
//map<int> mp;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int zx){
    if(zx<0){zx=-zx;putchar('-');}
    if(zx<10) putchar(zx+'0');
    else{
        write(zx/10);
        putchar(zx%10+'0');
    }
}
int sum[500001],n,d1[500001],d2[500001],ans;
void Pri(){
    for(int i=1;i<=n;i++){
        for(int j=2;j<=n/i;j++){
            if(i*j>n) break;
            sum[i*j]+=i;
        }
    }
}
void dp(){
    for(int i=n;i>=1;i--){
        if(sum[i]<i){
            if(d1[i]+1>d1[sum[i]]){
                d2[sum[i]]=d1[sum[i]];
                d1[sum[i]]=d1[i]+1;
            }else if(d1[i]+1>d2[sum[i]]) d2[sum[i]]=d1[i]+1;
        }
    }
}
int main(){
    n=read();
    Pri();
    dp();
    for(int i=1;i<=n;i++) ans=max(ans,d1[i]+d2[i]);
    write(ans);putchar('\n');
    return 0;
}