注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

HDU 1058 && HDU 3199  

2011-11-02 20:28:21|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=1058

http://acm.hdu.edu.cn/showproblem.php?pid=3199

1058代码:

#define N 5843
int
f[N];
int
min(int a,int b,int c,int d)
{
 
  a
=a>b?b:a; 
  c
=c>d?d:c; 
  a
=a>c?c:a;
  return
a;
}

int main
()
{

  int
a,b,c,d,i,n;
  a=b=c=d=1;
  f[1]=1;
  for
(i=2;i<=N;i++)
  {

    f[i]=min(f[a]*2,f[b]*3,f[c]*5,f[d]*7);
    if
(f[i]==f[a]*2)
      a++;
    if
(f[i]==f[b]*3)
      b++;
    if
(f[i]==f[c]*5)
      c++;
    if
(f[i]==f[d]*7)
      d++;
  }

  while
(scanf("%d",&n)==1&&n)
  {

    if
(n%100==11||n%100==12||n%100==13) printf("The %dth humble number is %d.\n",n,f[n]);
    else

    {

      if
(n%10==1)
        printf("The %dst humble number is %d.\n",n,f[n]);
      else if
(n%10==2)
        printf("The %dnd humble number is %d.\n",n,f[n]);
      else if
(n%10==3)
        printf("The %drd humble number is %d.\n",n,f[n]);
      else

        printf("The %dth humble number is %d.\n",n,f[n]);
    }
  }
}

小结:该题一上来可能会想到暴力,直接打表,其实可以,但是假如题目增大数据量,要使用大数或者数组开不了那么大,这种办法就报废了。暴力算法的基本思路是:从1到MAX(一个很大的数)逐一验证是否满足Humble Number的要求,然后开数组保存。

其实我们可以这么分析,把每个Humble Number都分解成2^a*3^b*5^c*7^d,例如1就是a=0,b=0,c=0,d=0(简写成0000,下同),那么2就是1000,3则为0100,4为2000、、、、、以此类推。那么这个得到的数的顺序是怎么样的呢?例如随便举例1221与2112谁大谁小?有人说直接乘出结果1221对应2*3*3*5*5*7,2112对应2*2*3*5*7*7,但是数据大了以后呢?所以这里应用到动态规划的思想,通过把前面计算过的结果保留下来,通过一个min函数去确定较小的数,一次后推,这样就可以确定顺序了。具体代码上面已经展示。

①输出的地方注意一些细节,注意英语的序数词的一些变化。

②如果不确定数据的大小,最好使用__int64,或者出错时使用大数。

③不要被题目的数据吓到,要沉下心去分析,或许只是一道水题。

 

3199代码:

#include <stdio.h>

__int64
s[10001];
__int64
min_num(__int64 a,__int64 b,__int64 c)
{

     __int64
min=a;
     if
(b<min) min=b;
     if
(c<min) min=c;
     return
min;      
}

int
main()
{

    int
p[3],x,i,j,temp;
    int
a,b,c;
    while
(scanf("%d%d%d%d",&p[0],&p[1],&p[2],&x)==4)
    {

        a=b=c=0;
        for
(i=0;i<3;i++)
            for
(j=i+1;j<3;j++)
            {
if(p[i]>p[j]) {
                      temp=p[i];
                      p[i]=p[j];
                      p[j]=temp;            
                 }                 
            }

       s[0]=1;
       for
(i=1;i<=x;i++)
       {

             s[i]=min_num(s[a]*p[0],s[b]*p[1],s[c]*p[2]);
             if
(s[i]==s[a]*p[0]) a++;
             if
(s[i]==s[b]*p[1]) b++;
             if
(s[i]==s[c]*p[2]) c++;                
       }

       printf("%I64d\n",s[x]);                           
    }

    return
0;   
}

3199的思路与Humble Numbers无异,只是注意输入时数字需要额外排序,因为给定的不一定是升序的。其他思路详见上述代码。


(好久都想写解题报告了,這是第一篇,要有一个好的开头!AC!加油!)
  评论这张
 
阅读(174)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018