Blog·Tanky WooABOUTRSS

HDU/HDOJ 1128 Self Numbers(暴力题,水题)

30 Jun 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1128

暴力即可,不过这里先开始我给TLE了,因为我把每一个数,都从他的d(n),  d(d(n))...都算了,遍历从1~1000000   =。=

其实再想想,只需要算d(n)即可,然后遍历1~1000000,因为比如d(...d(n))是x,则d(x)任然会在后面遍历到。。。

AC代码:

// Author: Tanky Woo
// Blog: www.WuTianQi.com
// Title: HDOJ 1128 Self Numbers
// About: 

#include 
#include 
#include 
#include 
using namespace std;

bool hash[1000005];
int t1, t2;
/*
inline void fun(int n)
{
    while(n <= 1000000)
    {
        t1 = n;
        t2 = n;
        while(t1)
        {
            t2 += t1%10;
            t1 /= 10;
        }
        n = t2;
        hash[n] = 1;
    }
}
*/

inline void fun(int n)
{

        t1 = n;
        t2 = n;
        while(t1)
        {
            t2 += t1%10;
            t1 /= 10;
        }
        n = t2;
        hash[n] = 1;
}

int main()
{
    memset(hash, 0, sizeof(hash));
    for(int i=1; i<= 1000000; ++i)
        fun(i);
    for(int i=1; i<=1000000; ++i)
        if(hash[i] == 0)
            printf("%d\n", i);
    return 0;
}