夏令营501-511NOIP训练16—

传送门：QAQQAQ

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

思路：YY一下，若$x$可以变为$y$，则$y$也一定能变为$x$，所以我们对于可以互相变换的点建一条无向边，因为每一个点最多之和一个值比它小的点连边，所以不可能出现环（这点可以人工YY证明）

所以我们在这个无环“森林”中跑一个最长链即可

代码：（其实以1为根跑直径不够严谨，用DP算最长链更好）

#include<bits/stdc++.h>

using namespace std;

vector<int> v[];

int d[];

void dfs(int u,int f,int depth)

{

    d[u]=depth;

    for(int i=;i<(int)v[u].size();i++)

    {

        if(v[u][i]==f) continue;

        dfs(v[u][i],u,depth+);

    }

}

void init(int n)

{

    for(int i=;i<=n;i++)

    {

        int sum=;

        for(int j=;j*j<=i;j++)

        {

            if(i%j==)

            {

                sum+=j;

                if(j*j!=i&&j!=) sum+=i/j;

            }

        }

        if(sum<i)

        {

            v[sum].push_back(i);

            v[i].push_back(sum);

        }

    }

//  for(int i=1;i<=n;i++)

//  {

//      cout<<i<<":";

//      for(int j=0;j<v[i].size();j++) cout<<v[i][j]<<" ";

//      cout<<endl;

//  }

}

int main()

{

    int n; cin>>n;

    init(n);

    dfs(,-,);

    int s=-,maxn=-;

    for(int i=;i<=n;i++)

    {

        if(maxn<d[i])

        {

            maxn=d[i];

            s=i;

        }

    }

    dfs(s,-,);

    for(int i=;i<=n;i++)

    {

        if(maxn<d[i]) maxn=d[i];

    }

    cout<<maxn<<endl;

    return ;

}

巴特西

夏令营501-511NOIP训练16——数字转换

最新文章

热门文章