UVa 1583 - Digit Generator 解题报告 - C语言
2024-09-30 14:27:47
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版) 刘汝佳 编著
最新文章
- Nodejs之MEAN栈开发(五)---- Angular入门与页面改造
- 信息中心网络 ,Information-centric networking, ICN
- ACM 喷水装置(一)
- font awesome
- OSVERSIONINFO
- prim模板
- HDU--杭电--3790--最短路径问题
- iOS UIAlertView 文字对其方式 文字大小 设置方法
- 关于PHP输出字符串多了两个字节的BUG
- Windows server 安装 OpenSSH
- 用java代码解决excel打开csv文件乱码问题
- JAVA中对字符串的常见处理函数汇总
- SpringMVC接受JSON参数详解及常见错误总结我改
- Ambertools15安装(详细)
- Linux运维之——每日小技巧,谈进程与线程的区别
- 适配器(GOF23)
- LeetCode: Add Binary 解题报告
- Windows: 如何配置IPv6隧道
- nginx 1.12 配置解析php
- 搞笑入群二维码在线生成源码 php图片合成并添加文字水印