51nod 1010 只包含因子2 3 5的数 && poj - 1338 Ugly Numbers(打表)-白红宇

51nod 1010 只包含因子2 3 5的数 && poj - 1338 Ugly Numbers(打表)

阅读量：4360 次

发布时间：2019-06-07

本文共 2886 字，大约阅读时间需要 9 分钟。

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1010

http://poj.org/problem?id=1338

首先poj这题要找出第n个丑数,想到要打表,因为每一个丑数都是由前一个丑数*2或者*3或者*5得到,每次取3种结果种较小的那一个放入数组中.

打表的时候要注意保持数组有序.

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  15 #include 
                   
                    16 //#pragma comment(linker, "/STACK:102400000,102400000")17 #define CL(arr, val) memset(arr, val, sizeof(arr))18 19 #define ll long long20 #define inf 0x7f7f7f7f21 #define lc l,m,rt<<122 #define rc m + 1,r,rt<<1|123 #define pi acos(-1.0)24 25 #define L(x) (x) << 126 #define R(x) (x) << 1 | 127 #define MID(l, r) (l + r) >> 128 #define Min(x, y) (x) < (y) ? (x) : (y)29 #define Max(x, y) (x) < (y) ? (y) : (x)30 #define E(x) (1 << (x))31 #define iabs(x) (x) < 0 ? -(x) : (x)32 #define OUT(x) printf("%I64d\n", x)33 #define lowbit(x) (x)&(-x)34 #define Read() freopen("a.txt", "r", stdin)35 #define Write() freopen("b.txt", "w", stdout);36 #define maxn 101037 #define maxv 101038 #define mod 100000000039 using namespace std;40 ll p[1555];41 int main()42 {43 //freopen("a.txt","r",stdin);44 int i=1,j=1,k=1;45 p[1]=1;46 for(int l=2;l<=1500;l++)47 {48 p[l]=min(p[i]*2,min(p[j]*3,p[k]*5));49 if(p[l]==p[i]*2) i++;50 if(p[l]==p[j]*3) j++;51 if(p[l]==p[k]*5) k++;52 //printf("%lld\n",p[l]);53 }54 int n;55 while(~scanf("%d",&n)&&n)56 {57 printf("%lld\n",p[n]);58 }59 return 0;60 }

51nod这题让你求>=n的丑数,因为n很大,所以打完表后需要二分查找,打表的时候要注意直到大于10^18,上限可以自己试几次.

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  15 #include 
                   
                    16 //#pragma comment(linker, "/STACK:102400000,102400000")17 #define CL(arr, val) memset(arr, val, sizeof(arr))18 19 #define ll long long20 #define inf 0x7f7f7f7f21 #define lc l,m,rt<<122 #define rc m + 1,r,rt<<1|123 #define pi acos(-1.0)24 25 #define L(x) (x) << 126 #define R(x) (x) << 1 | 127 #define MID(l, r) (l + r) >> 128 #define Min(x, y) (x) < (y) ? (x) : (y)29 #define Max(x, y) (x) < (y) ? (y) : (x)30 #define E(x) (1 << (x))31 #define iabs(x) (x) < 0 ? -(x) : (x)32 #define OUT(x) printf("%I64d\n", x)33 #define lowbit(x) (x)&(-x)34 #define Read() freopen("a.txt", "r", stdin)35 #define Write() freopen("b.txt", "w", stdout);36 #define maxn 101037 #define maxv 101038 #define mod 100000000039 using namespace std;40 ll p[10999];41 42 ll erfen(ll n)43 {44 int l=1,r=10999;45 while(l<=r)46 {47 int mid=(l+r)/2;48 if(p[mid]==n) return p[mid];49 else if(p[mid]>n) r=mid-1;50 else l=mid+1;51 }52 if(p[l]

转载于:https://www.cnblogs.com/nowandforever/p/4569165.html

你可能感兴趣的文章