站长工具

数字转换

作者：hxss

题目描述

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

输入格式

输入一个正整数 n。

输出格式

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

数据范围

1≤n≤50000

输入样例

7

输出样例

3

样例解释

一种方案为：4→3→1→7。

题目分析

image
image

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int N=5e4+5,M=2*N;
int h[N],e[M],ne[M],idx;
int sum[N],vis[N],ans;
void add(int x,int y){
	e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
int dfs(int u,int f){
    //标记该结点已被访问
	vis[u]=1;
	int dist=0,d1=0,d2=0;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		//防止回头
		if(j==f)continue;
		//求当前结点向下的路径
		int dis=dfs(j,u)+1;
		//更新该结点向下的最长路径
		dist=max(dist,dis);
		//更新最长路径和次长路径
		if(dis>d1)d2=d1,d1=dis;
		else if(dis>d2)d2=dis;
	}
	//答案即为每个结点的最长路径和次长路径之和的最大值
	ans=max(ans,d1+d2);
	return dist;
}
signed main(){
	int n;
	cin>>n;
	memset(h,-1,sizeof h);
	//遍历一下，将i*j的约数和算出来
	for(int i=1;i<=n/2;i++){
		for(int j=2;j<=n/i;j++)sum[i*j]+=i;
	}
	//如果约数之和比本身小，则建立无向边
	for(int i=2;i<=n;i++){
		if(sum[i]<i){
			add(i,sum[i]);
			add(sum[i],i);
		}
	}
	//由于本题可能是森林，不一定是树
	//如果不想去证明的话，为了保证正确性还是遍历一下所有未被标记的结点
	for(int i=1;i<=n;i++)if(!vis[i])dfs(i,-1);
	cout<<ans<<endl;
	return 0;
}
本文转载于网络 如有侵权请联系删除

相关文章

  • 叫板DALL·E 2，预训练大模型做编码器，谷歌把文字转图像模型卷上天

    来源：机器之心本文约3400字，建议阅读8分钟本文介绍了来自谷歌的研究者也在OpenAI做出了探索，提出了一种文本到图像的扩散模型Imagen。复制OpenAI：DALL・E2就是最好的。谷歌：看下我们Imagen生成的柴犬？多模态学习近来受到重视，特别是文本-图像合成和图像-文本对比学习两个方向。一些模型因在创意图像生成、编辑方面的应用引起了公众的广泛关注，例如OpenAI的文本转图像模型DALL・E、英伟达的GauGAN。现在，来自谷歌的研究者也在这一方向做出了探索，提出了一种文本到图像的扩散模型Imagen。Imagen结合了Transformer语言模型和高保真扩散模型的强大功能，在文本到图像的合成中提供前所未有的逼真度和语言理解能力。与仅使用图像-文本数据进行模型训练的先前工作相比，Imagen的关键突破在于：谷歌的研究者发现在纯文本语料库上预训练的大型LM的文本嵌入对文本到图像的合成显著有效。Imagen的文本到图像生成可谓天马行空，能生成多种奇幻却逼真的有趣图像。比如正在户外享受骑行的柴犬：泰迪熊的400米蝶泳首秀：狗狗照镜子发现自己是只猫：火龙果成精要打空手道了：如果你

  • float现象（是什么,脱标,排序,贴靠,字围,高度问题）

    1：网页的布局方式<!DOCTYPEhtml> <htmllang="en"> <head> <metacharset="UTF-8"> <metaname="viewport"content="width=device-width,initial-scale=1.0"> <title>Document</title> <styletype="text/css"> *{padding:0px;margin:0px;} .box1 { width:100px; height:100px; background-color:red; float:left; } .box2 { width:100px; height:100px; background-color:blue; float:right; margin-right:100px; } </style> </head>

  • 快速入门网络爬虫系列 Chapter16 | 爬虫性能提升

    一、基础简介1、任务调度操作系统通常采用时间片轮转的抢占式调度方式 一个任务执行一段时间后强制暂停，去执行下一个任务 每个任务轮流执行 2、线程与进程2.1、进程具有独立功能的程序在数据集合上的一次动态执行过程 系统进行资源分配和调度的一个独立单位 任务调度的最小单位 以资源管理器为例 2.2、线程线程是CPU调度和分派的基本单位 能独立运行 基本上不拥有系统资源，可与通一个进程的其他线程共享进程的资源 一个进程中可以有多个线程 线程与进程的关系2.3、线程与进程的联系线程被称为轻量级进程，和进程一样拥有独立的执行控制 一个进程包含多个线程，线程是进程对的一个实体 一个线程可以创建和撤销所属进程中的另一个线程 同一个进程中的多个线程之间可以并发执行 2.4、线程与进程的区别线程不像进程一样拥有独立的内存空间 线程和所属进程的其他线程共享内存空间 线程之间的通讯更加简单 3、多线程目前为止，开发的爬虫都属于单线程，不能充分利用硬件资源和带宽资源 多线程是一种常用的提高效率的手段，可以提升网络爬虫性能 Python语言中的threading库提供易用的对线程API 3.1、多线程的原理在同

  • 微信拍一拍，每天赚一顿早饭钱？

    微信拍一拍这功能推出有一个多月了，在6月18日我整理了篇介绍微信拍一拍趣味玩法的文章，顺带着做了个辅助生成拍一拍文字的小程序：当时也在考虑这个拍一拍究竟之后会衍生出什么新的功能。没想到后续iOS最新版微信率先在个人设置页推出了拍一拍的设置选项，部分手机型号的安卓版本目前也可以使用，仍有部分安卓版还没能实现设置：拍一拍设置现在过去这么久，我仍没琢磨明白拍一拍的价值在哪，但没想到上面做出来的小程序却实实在在每天给我带来了利益价值！从6月18小程序正式上线，到6月20号达到投放广告的门槛，再到整整一个月7月18日，这小程序为我带来了282.35元的收入，大概的明细如下：是的，金额看着没有那么让人振奋，真正让我觉得有意义的是累计用户数，在整整一个月后，小程序“拍一拍小尾巴”已经有6.6万累计用户了！这个增长过程，除了开头那篇介绍的文章有推广、大概两千多阅读量，基本是通过用户自行搜索和扩散完成的：而且，随着目前用户体量的增加，日均访问最近达到了3k+，虽然我对小程序数据研究不深，也能隐约感觉到不出意外的话，累计用户10w+应该是能达到的！前几天跟朋友聊，当时还开玩笑说可能这辈子能靠自己接触10w

  • 如何在 CentOS 8 上安装 OpenCV

    OpenCV(OpenSourceComputerVisionLibrary)是一个开源的计算机视觉库，支持所有主流操作系统上的C++，Python，和Java。它可以发挥多核进程和GPU加速，用于实时操作。OpenCV应用广泛，包括医疗图片分析，街景图片处理，监视视频，探测和识别面部，追踪移动物体，提取3D模型，等等。本文描述如何在CentOS8上安装OpenCV。想要安装最新稳定版本的OpenCV，滚动到从源码安装OpenCV一节。请选择最适合你的安装方式。一、从CentOS源仓库安装OpenCVOpenCV软件包在CentOS8标准软件源中可用，但是没有Python的版本。安装OpenCV软件包，输入：sudodnfinstallopencvopencv-developencv-python复制一旦安装完成，验证OpenCV是否存在，输入：pkg-config--modversionopencv复制3.4.1复制二、从源码安装OpenCV从源码安装OpenCV可以允许你安装最新可用的版本。它还将针对你的特定系统进行优化，并且你可以完整控制所有的构建选项。执行下面的步骤，从源码安装

  • Work at home, Work as a distributed team | TVP思享

    Tetrate.io是一家北美的企业级ServiceMesh服务商，提供基于Istio,Envoy,SkyWalking的企业级ServiceMesh产品：TetrateServiceBridge。Tetrate.io创立之初就是以分布式团队、在家办公为工作模式，所有成员都不在统一办公地点工作。目前，公司团队分布于北美，欧洲，中国，东南亚等多个国家。本文是对TVP吴晟老师的直播演讲整理，分享在分布式工作模式下，如何保证高效沟通。「TVP思享」专栏，凝结大咖思考，汇聚专家分享，收获全新思想，欢迎长期关注。一、 分布式工作的背景和难点1.Tetrate成立背景我们公司是在前年成立，下图所列是最早期的所有的技术团队成员，涵盖了全球绝大部分的时区，包括日本、中国、印度等。随着团队人数越来越多，其中有一些同事，并不总是固定在一个时区。例如有的同事有段时间在北美，其他的时间在日本，包括我自己每年也会有大量的出差，会频繁切换自己的时区。这样可以带来一个好处，除了大家能够保持一致的协作模式外，也可以有更多的私人时间，这是我们公司的经历背景。其实现在有非常多有名的上市公司，都在以远程协作的方式来工作，基

  • 老司机也该掌握的MySQL优化指南

    当MySQL单表记录数过大时，增删改查性能都会急剧下降，所以我们本文会提供一些优化参考，大家可以参考以下步骤来优化：一、单表优化除非单表数据未来会一直不断上涨，否则不要一开始就考虑拆分，拆分会带来逻辑、部署、运维的各种复杂度。一般以整型值为主的表在千万级以下，字符串为主的表在五百万以下是没有太大问题的，而事实上很多时候MySQL单表的性能依然有不少优化空间，甚至能正常支撑千万级以上的数据量。1字段尽量使用TINYINT、SMALLINT、MEDIUM_INT作为整数类型而非INT，如果非负则加上UNSIGNED；VARCHAR的长度只分配真正需要的空间；使用枚举或整数代替字符串类型；尽量使用TIMESTAMP而非DATETIME；单表不要有太多字段，建议在20以内；避免使用NULL字段，很难查询优化且占用额外索引空间；用整型来存IP。2索引索引并不是越多越好，要根据查询有针对性的创建，考虑在WHERE和ORDERBY命令上涉及的列建立索引，可根据EXPLAIN来查看是否用了索引还是全表扫描；应尽量避免在WHERE子句中对字段进行NULL值判断，否则将导致引擎放弃使用索引而进行全表扫描；

  • 程序员培训出身狂揽活，加班被同事嘲笑活该，网友：急于证明自己

    来源：综合自网络俗话说初生牛犊不怕虎，刚进入职场的人在工作上总是充满干劲，这份新鲜血液的注入也会给公司带来新的活力。就有一名培训出身的程序员加入新公司，因为表现过于“耀眼”被同事孤立，该同事还吐槽称：公司上个月招了一个培训出身的技术，一点都不谦虚。会上领导提了很多需求让大家一周搞定，因为任务时间过于紧所有人都没有吭声，就他说了一句“小case”，没想到他还真给搞定了。他急着向老板邀功，老板就把这个月的大半需求都交给他做了，现在我们这些同事就看着他天天一个人加班...哎！活该他加班。发帖的同事还表示：他是不知道公司老板用起培训的人一点都不留情的，他既然急于表现自己就活该天天加班呗。而对于同事都孤立这名新来的程序员，网友表示：他新来的不懂你们的职场规矩，打破了你们之前与老板之间的平衡关系。虽然老板在使劲用他，看似他吃亏，但是你们也危险了，在老板眼中既然培训班的这么好用又便宜，以后老板就招培训班出来的了，一个一个把你们都干掉。还有网友力挺这种不怕吃亏的职场新人，表示：虽说他不是科班出身的程序员，但是进入你们这一群科班出身的公司就说明他能力不比你们差。也许他是急于在老板面前表示立功，可是这动机

  • Angular技巧汇总 原

    一、声明全局的类型定义  声明项目的全局类型，同时不需要在各个Ts文件中import{XXX}from'xxx' ，就能直接引用！方法是：     增加src/typings.d.ts文件，在文件中增加 interfaceIName{ name:string;}的类型定义。   那么IName这个类型在所有的TS文件中自动可以访问！     注意：不要在代码前增加 export的关键字。    参考：3rdPartyLib二、在懒加载指定模块前，动态加载一个js文件。   通常我们在项目中引用第三方包，一种是import方法，其代码最终是打包一起；一种是配置angular.json文件，其中有scripts:[]，在里面增加相应的js完整路径达到引用js文件，其代码不参与构建，会在首页加载时，做为普通的外挂脚本文件引入。   无论是打包在一起，还是外挂脚本，都是会增加初始加载的负担！比如echarts.js有800kb的大小，在初始的登录页面，用户根本用不到图表的功能，甚至进入主界面的模块后，也不需要加载它，当仅我在点击到某些有图表页面的页面时，才必须加载echar

  • 广东人，请收藏这个超级方便的小程序

    广东人，热辣的5月好! 今天有个小程序交付给你啦。 以前去各个窗口跑腿办事，口水与汗水齐飞，办个证下来，都足够微信捐步了。 后来有了微信公众号、服务号，办各种事务总算方便了。但一口气关注公安、社保、公积金、驾照......有时候也是犯愁。 今天，我们想了个办法，让它更简单、方便。 把所有事情，装进一个小程序！ 今天，全国首个集成民生服务微信小程序“粤省事”及同名服务号正式上线发布。 长按扫码体验 正式介绍一下：这是广东“数字政府”改革建设的阶段性成果，也是数字广东网络建设有限公司积极响应广东数字政府改革建设的首个成果。 那....它到底方便在哪？ 最全业务集合，办事不用再翻找 不用再翻找，那“粤省事”小程序里有什么？ 首期上线的142项政务服务事项，涉及驾驶证、行驶证、出入境证件（港澳通行证、中国台湾通行证、护照）、残疾人证、出生证和居住证等十大证件服务；社保医保、住房公积金服务；残疾人、外来务工人员、老年人等几大特殊群体专门服务等等。 比如：一站式实现公积金各类业务 比如：开车忘带驾驶证、行驶证可提供二维码供交警查验证件 比如：护照、通行证一键续签 另外，打开“我的证件”，即可查看到

  • MySQL之ROUND函数四舍五入的陷阱

    FullSizeRender2TOC在MySQL中，ROUND函数用于对查询结果进行四舍五入，不过最近使用ROUND函数四舍五入时意外发现并没有预期的那样，本文将这一问题记录下来，以免大家跟我一样犯同样的错误。问题描述假如我们有如下一个数据表test，建表语句如下CREATETABLEtest(复制idint(11)NOTNULLAUTO_INCREMENT,复制field1bigint(10)DEFAULTNULL,复制field2decimal(10,0)DEFAULTNULL,复制field3int(10)DEFAULTNULL,复制field4float(15,4)DEFAULTNULL,复制field5float(15,4)DEFAULTNULL,复制field6float(15,4)DEFAULTNULL,复制PRIMARYKEY(id)复制)ENGINE=InnoDBDEFAULTCHARSET=utf8;复制我们创建了一个名为test的表，出了id字段之外还包含了多个字段，拥有这不同的数据类型。我们向这个表中插入一条数据INSERTINTOtest(field1,fie

  • Salesforce创始人:所有企业都将是APP企业 2015企业必须关注的三大技术趋势

    2014年我们真正领略到了第三次技术浪潮的威力，社交媒体、智能硬件、可穿戴设备、物联网、大数据、云计算、人工智能，所有这些技术元素拼装成了一组完整的新财富基因，每一个行业，每一个企业，都面临着一个选择：颠覆，或者被颠覆。 2015年，能够抓住技术革命机遇的企业将获得巨大竞争优势，而那些嗅觉迟钝，行动缓慢的企业将以前所未有的速度被淘汰，留给企业决策者的觉悟时间其实已经非常有限。 以下是Salesforce联合创始人ParkerHarris近日对2015年企业技术趋势做出预测，也可以看做是给所有企业家和技术决策者们的忠告：一、所有企业都将是APP企业所有的企业领导者都应当成为技术领袖，因为应为今天每个行业都在涌现Netflix或Uber这样的颠覆性企业。App是这次技术颠覆的主要载体，所有的企业都应当成为APP企业。如今80%的财富500强企业都已经开发APP与顾客、供应商和合作伙伴更好地沟通。2015年，将会有更多的APP承载关键业务功能。 二、业务分析的数据孤岛将消失新的一年中，那些领先企业都将遵循这样一个天条：不得有信息孤岛。大数据已经不再仅仅是一个时髦名词，数据分析将不再限于

  • python h5文件读取_python读取整个txt文件

    大家好，又见面了，我是你们的朋友全栈君。这篇文章是一个工具类，用来辅助医学图像分割实战unet实现(二）4、数据存储这一小节的内容。2019/5/2更新：HDF5DatasetWrite可以动态扩展储存大小文件：HDF5DatasetGenerator.py#-*-coding:utf-8-*- importh5py importos importnumpyasnp classHDF5DatasetGenerator: def__init__(self,dbPath,batchSize,preprocessors=None, aug=None,binarize=True,classes=2): self.batchSize=batchSize self.preprocessors=preprocessors self.aug=aug self.binarize=binarize self.classes=classes self.db=h5py.File(dbPath) self.numImages=self.db["images"].shape[0] #self.

  • System.out 和 System.err 的区别

    System.out和System.err的区别，很基础吧，   但是仔细观察idea的后台日志，你会有新的发现。   测试一段极其简单的代码： publicclassTestBasic{ publicstaticvoidmain(String[]args){ System.out.println("testSystem.out="+111); System.err.println("testSystem.err="+222); System.out.println("testSystem.out="+111); System.err.println("testSystem.err="+222); System.out.println("testSystem.out="+111); System.err.println("testSystem.err="+222); } }复制   结果：     第一个问题：为什么System.out和System.err 的打印结果有不同的颜色 估计是idea的控制台的默认的人性

  • 异常处理（面试题）

    一、关于异常的一些面试题 1、请说明throws和throw的区别?2、请说明Exception和RuntimeException的区别和关系?3、请说明Error和Exception的区别和联系?4、请说出五个常见的RuntimeExcetion5、请说明异常处理的流程? 1、请说明throws和throw的区别? 答: throws: I-抛出的是在方法体中可能出现的异常，抛给调用处处理|-声明的位置是在方法名之后 throw: |-抛出的手工实例化的异常对象（我们自己创建的一个异常对象)，相当于程序出现了一个异常。 |-声明的位置是在方法体之内 2、请说明Exception和RuntimeException的区别和关系? 答: Excetion是RuntimeException的父类 Exception类型的异常需要强制进行处理，如果不处理编译无法通过。 RuntimeException类型异常叫做运行时异常不需要强制处理   3、请说明Error和Exception的区别和联系? 答: Error和Exception都是Throwable的子类

  • redux小案例

           

  • P1220 关路灯

    感谢所有AC 传送门 经验     当遇到动点的$dp$问题时，需要注意动点所在位置对状态转移的影响，如果有影响，可以适当考虑增加一个维度用来表示动点地位置状态。 思路     由于老李关掉灯的时间忽略不计，因此老李所过之处一定是所有灯全灭，那么关灯就可以有两种选择，一种是沿着现在行进的方向继续关下一盏灯，另一种是掉头去关另一盏灯。可以用状态$f(i,j)$来表示老张从$i$走到$j$时灯的总能耗。接下来考虑状态转移，即关灯的选择。     因为老李的位置未知，初步判断$f(i,j)$可以分别由$f(i+1,j)$和$f(i,j+1)$，代表着老李两个不同的行进方向。但是问题又来了，转移的时候，并不知道老李的位置，可是老李的位置又和灯的耗能息息相关，因此我们必须要表示出老李的位置。于是定义状态$f(i,j,0)$表示老李关掉了$i$到$j$的灯且最后站在$i$点时灯的总能耗，$f(i,j,1)$表示老李关掉了$i$到$j$的灯且最后站在$j$点时灯的总能耗。 &nbs

  • 二维表转树结构

    publicclassUnitTest1 { [TestMethod] publicvoidTestMethod1() { varnodes=newList<Node>() { newNode{Id=1,PId=null,Data="学校"}, newNode{Id=2,PId=null,Data="医院"}, newNode{Id=3,PId=1,Data="小学"}, newNode{Id=4,PId=3,Data="一年级"}, newNode{Id=6,PId=4,Data="张三"}, newNode{Id=5,PId=2,Data="浙江附属医院"}, }; ToTree(nodes); } publicvoidToTree(List<Node>nodes,Nodenode=null) { if(node==null) { varparents=nodes.FindAll(f=>f.PId==null); foreach(variteminparents) { ToTree(nodes,item); } } elseif(nodes.Ex

  • Taro + TS 项目取别名配置 alias

    最近在用taro3.X做小程序项目、项目尝试加入ts做demo，在ts文件中引入文件要'../../../'就发现很丑，所以做了配置取别名 当我们平时在js文件中配置时，js文件引入是没有问题的 alias:{ '@':path.resolve(__dirname,'..','src') }, 复制 　　    但是在ts文件中就会报红      我们需要在 tsconfig.json文件中的 compilerOptions中加入 "baseUrl":"./src", "paths":{ 　"@/*":["./*"] } 复制 　　      保存就会发现没有报红了       

  • java判空工具类

    复制 importjava.lang.reflect.Field; importjava.lang.reflect.Method; importjava.text.SimpleDateFormat; importjava.time.LocalDate; importjava.util.Collection; importjava.util.Date; importjava.util.Map; /** *@program: *@description: *@author:Dong *@create:2021-04-0718:08 **/ publicclassEmptyUtils{ privateEmptyUtils(){ } /** *======================================== * *@paramobj *@returnboolean *@throws *@方法说明：空判断空返回true *@author:missyouBUG *@创建时间：2020/7/911:14 *====================================

  • thinkphp5.1 - twig使用

    thinkphp5.1-twig使用1、安装按照：https://github.com/yunwuxin/think-twigTwigTemplateForThinkPHP5 安装 composerrequireyunwuxin/think-twig使用 配置文件里template.type=Twig即可 2、使用：publicfunctionindex(){return$this->fetch("index");} 参考：其他人写的扩展：https://github.com/wdaglb/thinkphp-twig

相关推荐

推荐阅读