UVa 1583 - Digit Generator 解题报告 - C语言_weixin_30877181的博客-程序员宝宝

技术标签: c/c++  

1.题目大意

如果a加上a的各个数字之和得到b,则说a是b的生成元。给出n其中$1\le n\le 100000$,求其最小生成元,若没有解则输出0。

 

2.思路

使用打表的方法打出各个数字a对应的b,存入s[b]中。

 

3.应注意的问题

(1) 没有解时输出0,也就意味着在开始打表前要把数组s[maxn]清零。利用memset实现,要加入string.h的头文件,而memset对数组操作时只能初始化为0或-1。

(2) 要求求出的是最小生成元,也就意味着在存入s[b]之前要有所比较。

 

4.代码

#include"stdio.h"
#include"string.h"
#define maxn 100005
int s[maxn];
int main()
{
    int i,T,n,a,b;
    memset(s,0,sizeof(s)); //数组清零
    for(i = 1; i < maxn ; i++)
    {
        a = i;
        b = i;
        while(a > 0)    //原数加上其各个数字之和得到a
        {
            b += a%10;
            a /= 10;
        }  
        if((s[b]==0) || (s[b]>i))  //确保其是最小生成元
            s[b] = i;
    }
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",s[n]);
    }
    return 0;
}

  

 

参考书目:算法竞赛入门经典(第2版) 刘汝佳 编著

转载于:https://www.cnblogs.com/rgvb178/p/5947701.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30877181/article/details/96449528

智能推荐

CRM后台管理系统:HTML+CSS+JavaScript制作企业网站后台管理系统模板网站(46个页面)[email protected]码住夏天-web网页设计的博客-程序员宝宝

CRM后台管理系统:HTML+CSS+JavaScript制作企业网站后台管理系统模板网站(46个页面) 一款使用Bootstrap构建,多个主页版本的企业网站后台管理系统,咨询管理,数据统计后台管理ui框架模板下载。包含多个ui工具包,带企业管理系统ui组件等。支持响应式布局...

Binding的Parse和Format事件_weixin_34390105的博客-程序员宝宝

做数据处理程序的程序员一定都很烦数据库的数据类型和开发语言数据类型的不一致问题(使用ORM的情况除外)。当然这个问题也一定程度上是数据库设计的欠缺造成的。现在举个例子来讲一下如.NET中如何通过DataBinding来提高程序开发中的转换效率,相信如下的情景一定有很多人遇到过。问题描述:数据中的日期型字段设置成了String型或者Float型而,程序设计时用的日期选取空间一般用Date...

(百例编程)55.哪个大夫哪天值班_foolbread的博客-程序员宝宝

题目:医院有A、B、C、D、E、F、G七位大夫,在一星期内(星期一至星期天)每人要轮流值班一天。现在已知:A大夫比C大夫晚一天值班;D大夫比E大夫晚二天值班;B大夫比G大夫早三天值班;F大夫的值班日在B和C大夫的中间,且是星期四;请确定每天究竟是哪位大夫值班?/*题目:医院有A、B、C、D、E、F、G七位大夫,在一星期内(星期一至星期天)每人要轮流值班一天。现在已知:

局域网实现VLAN配置实例_普通网友的博客-程序员宝宝

计算机网络技术的发展犹如戏剧舞台,你方唱罢我登台。从传统的以太网(10Mb/s)发展到快速以太网(100Mb/s)和千兆以太网(1000Mb/s)也不过几年的时间,其迅猛的势头实在令人吃惊。而现在中大型规模网络建设中,以千兆三层交换机为核心的所谓“千兆主干跑、百兆到桌面”的主流网络模型已不胜枚举。现在,网络业界对“三层交换”和VLAN这两词已经不感到陌生了。 一、什么是三...

MongoDB学习分享&nbsp;&nbsp;泽0715&nbsp;新浪博客_lyp0715的博客-程序员宝宝

个人官方网站 :点击进入一: 下载     上MongoDB官网 ,我们发现有32bit和64bit,这个就要看你系统了,不过这里有两点注意:        ①:根据业界规则,偶数为“稳定版”(如:1.6.X,1.8.X),奇数为“开发版”(如:1.7.X,1.9.X),这两个版本的区别相信大家都知道吧。        ②:32bit的mongodb最大只能存放2G的数据

安装DB2后,新建db2admin管理员账户Administrator不显示的解决办法。_weixin_34178244的博客-程序员宝宝

今天装完DB29.7企业版之后,由于新建的db2admin管理员账户,导致下次开机的时候,Administrator用户隐藏起来了,Ctrl+del+alt才调出登陆窗口,很是麻烦。解决办法:修改注册表:开始-运行(Win+R)-regedit,进入注册表编辑器,然后:HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\W...

随便推点

Shader入门精要-3-中级篇_suixinger_lmh的博客-程序员宝宝

复杂光照、高级纹理、加入动态变量unity渲染路径(Rendering Path)前向渲染原理:unity中的前向渲染:unity渲染路径(Rendering Path)前向渲染原理:每个逐像素光源都要执行一个Passunity中的前向渲染:当渲染一个物体时,unity会计算哪些光源照亮了他以及照亮的方式【逐顶点,逐像素,球谐(SH)函数】。光源的类型 和渲染模式决定了光源对物体的照亮方式。Unity会对场景中光源的设置 和 光源对物体的影响程度(离物体远近,光强度等) 对光进行排序,

定时器/计数器0(计数器)_weixin_34262482的博客-程序员宝宝

/*效果说明: 计数器中断:通过外设计数是程序执行 按一下中断一次,中断发生时高四位亮,中断发生后又回到主程序*/ #include &lt;reg51.h&gt;#include &lt;stdio.h&gt;unsigned int i;void delay()//延时子函数{ i=50000; whil...

原生JavaScript实现form表单序列化的方法_weixin_34162401的博客-程序员宝宝

2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...

Invocation of init method failed; nested exception is org.hibernate.HibernateException: could not in..._weixin_30823683的博客-程序员宝宝

严重: Exception sending context initialized event to listener instance of class org.springframework.web.context.ContextLoaderListener org.springframework.beans.factory.BeanCreationException: Error creat...

又一位!发40篇SCI,90后博士受聘985教授_算法与数学之美的博客-程序员宝宝

最近一段时间,连续多位“90后”博导刷爆了很多人的朋友圈。从三年前引发舆论热议的学霸博导杨树、刘明侦,到前几天的刘琬璐……据不完全统计,目前国内高校和科研单位至少有10位“90后”教授。...

Delta File Fomat 2:扩展Spark读取Delta文件_wankunde的博客-程序员宝宝

文章目录DataSourceSpark 对外暴漏的读写文件的入口:writer.save() 方法DataFrameReader.load() 方法java.util.ServiceLoader扩展Spark 支持的DataSourceDataSourceDataSource 是Spark用来描述对应的数据文件格式的入口,对应的Delta也是一种数据文件格式,所以了解DataSource实现原...

推荐文章

热门文章

相关标签