UVa 1583 - Digit Generator 解题报告

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版）刘汝佳编著

巴特西

UVa 1583 - Digit Generator 解题报告 - C语言

最新文章

热门文章