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

系统管理员 2021-11-01 13:26 238阅读 0赞

传送门：[QAQQAQ][]

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

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

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
     
    vector<int> v[50005];
    int d[50005];
     
    void dfs(int u,int f,int depth)
    {
        d[u]=depth;
        for(int i=0;i<(int)v[u].size();i++)
        {
            if(v[u][i]==f) continue;
            dfs(v[u][i],u,depth+1);
        }
    }
     
    void init(int n)
    {
        for(int i=2;i<=n;i++)
        {
            int sum=0;
            for(int j=1;j*j<=i;j++)
            {
                if(i%j==0)
                {
                    sum+=j;
                    if(j*j!=i&&j!=1) 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(1,-1,0);
        int s=-1,maxn=-1;
        for(int i=1;i<=n;i++)
        {
            if(maxn<d[i])
            {
                maxn=d[i];
                s=i;
            }
        }
        dfs(s,-1,0);
        for(int i=1;i<=n;i++)
        {
            if(maxn<d[i]) maxn=d[i];
        }
        cout<<maxn<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11279755.html

[QAQQAQ]: https://dev.xjoi.net/contest/1212/problem/3
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/ebd0ad64adfc4b6494cad66d44bf2094.png