首页 > 代码库 > hdu 1058 Humble Numbers

hdu 1058 Humble Numbers

  这题应该是用dp来做的吧,但一时不想思考了,写了个很暴力的,类似模拟打表,然后排序即可,要注意的是输出的格式,在这里wa了一发,看了别人的代码才知道哪些情况没考虑到。

 1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #define For(i,s,t)    for(int i=s; i<=t; ++i) 6 using namespace std; 7 typedef long long LL; 8 const int inf= 2000000000; 9 10 LL value[6002];11 LL pw2[32]={1}, pw3[21]={1}, pw5[15]={1}, pw7[13]={1};12 13 int init(){14     For(i,1,31)   pw2[i]= pw2[i-1]<<1;15     For(i,1,20)      pw3[i]= pw3[i-1]*3;16     For(i,1,14)      pw5[i]= pw5[i-1]*5;17     For(i,1,12)      pw7[i]= pw7[i-1]*7;18     int num= 0;19     LL tmp1,tmp2,tmp3;20     for(int i=0; i<=31; ++i)21         for(int j=0; j<=20; ++j){22             if((tmp1= pw2[i]*pw3[j])> inf)    break;23             for(int k=0; k<=14; ++k){24                 if((tmp2= tmp1*pw5[k])> inf)    break;25                 for(int p=0; p<=12; ++p){26                     if((tmp3= tmp2*pw7[p])> inf)    break;27                     value[++num]= tmp3;28                 }29             }30         }31     sort(value+1,value+num+1);32     return num;33 }34 35 char s[4][5]= {"th","st","nd","rd"};36 37 int main(){38     int num= init(),n;39     while(~scanf("%d",&n),n)40         printf("The %d%s humble number is %lld.\n",n, n%10<=3 &&(n%100<11||n%100>13)? s[n%10]:"th", value[n]);41     return 0;42 }

  有空再回来写dp,今天看线段树看得一头雾水,唉~~

hdu 1058 Humble Numbers