首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。