UVA100[The 3n + 1 problem]

就是简单模拟,加记忆化,加线段树加速查询。


恩,注意输入中i和j不保证i<=j,就是这个让我WA2次。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-5-13


DESCRIPTION:


$DESCRIPTION


*/


#include <stdio.h>


#define MAXN 1000000


 


int f[MAXN+2];


int st[MAXN<<2];


 


int max(int a,int b)


{


    return a>b?a:b;


}


void build_segment_tree(int L=1,int R=MAXN,int root=1)


{


     if (L==R) st[root]=f[L];


     else


     {


         int LL=L,LR=(L+R)>>1,Lroot=root<<1;


         int RL=LR+1,RR=R,Rroot=Lroot|1;


         build_segment_tree(LL,LR,Lroot);


         build_segment_tree(RL,RR,Rroot);


         st[root]=max(st[Lroot],st[Rroot]);


     }


}


int get_max(int l,int r,int L=1,int R=MAXN,int root=1)


{


    if (r<L||l>R) return 0;


    if (l<=L&&R<=r) return st[root];


    else


    {


        int LL=L,LR=(L+R)>>1,Lroot=root<<1;


        int RL=LR+1,RR=R,Rroot=Lroot|1;


        return max(get_max(l,r,LL,LR,Lroot),


                   get_max(l,r,RL,RR,Rroot));


    }


}


 


int main()


{


    f[1]=1;


    for (int i=2;i<=MAXN;i++)


    {


        long long int n=i;


        int step=0;


        for (;;)


        {


            if (n<=MAXN&&f[n])


            {


               step+=f[n];


               break;


            }


            step++;


            if (n&1) n=((n<<1)|1)+n;


            else n>>=1;


        }


        f[i]=step;


    }


    build_segment_tree();


    int i,j;


    while (scanf(“%d%d”,&i,&j)!=EOF)


          if (i<=j) printf(“%d %d %d\n”,i,j,get_max(i,j));


          else printf(“%d %d %d\n”,i,j,get_max(j,i));


    return 0;


}