CODEVS——T 2969 角谷猜想

http://codevs.cn/problem/2969/

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 黄金 Gold

题解

查看运行结果

题目描述 Description

所谓角谷猜想，即给定一个正整数 n，对 n 反复进行下列两种变换：
1）如果n是偶数，就除以2；
2）如果n是奇数，就乘以3加1。
最后的结果总是1。

我们把从 n 变换到 1 所需要进行的变换次数称做 n 的变换长度，如数字 7 的变换为：

7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1

共进行了 16 次变换，因而 7 的变换长度为 16。

Wish 现在对一个给定区间内的最长变换长度比较感兴趣，但是手算起来计算量太大，于是他又找到了参加信息学竞赛的你，你可以帮助他吗？

输入描述 Input Description

每个测试点包含多组数据，第一行一个数 t，表示数据个数。
第二行至第 t+1 行，每行两个数 a、b，表示求 a 和 b 之间数（包含 a、b）的最长变换长度。

输出描述 Output Description

输出格式
t 行，每行输出对应输入数据的各个区间的最长变换长度。

样例输入 Sample Input

2
1 7
9 20

样例输出 Sample Output

16
20

数据范围及提示 Data Size & Hint

数据范围
1 <= t <= 100
1 <= a, b <= 10^8
区间长度不超过 10^5

记忆化、注意边界

没写returnWA半天zz啊

 #include <iostream>

 #include <cstdio>

 using namespace std;

 #define LL long long

 #define max(a,b) (a>b?a:b)

 #define min(a,b) (a<b?a:b)

 inline void read(LL &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 LL a,b,sum[];

 LL DFS(LL now)

 {

     if(now==) return ;

     if(now<)

     {

         if(sum[now]) return sum[now];

         else return now& ? sum[now]=DFS(now*+)+ : sum[now]=DFS(now>>)+;

     }

     else return now& ? DFS(now*+)+ :DFS(now>>)+;

 }

 int Presist()

 {

     int t;

     for(scanf("%d",&t); t--; )

     {

         LL ans=;    read(a),read(b);

         for(LL i=min(a,b); i<=max(a,b); ++i)

             ans=max(DFS(i),ans);

         printf("%lld\n",ans);

     }

     return ;

 }

 int Aptal=Presist();

 int main(){;}

巴特西

CODEVS——T 2969 角谷猜想

http://codevs.cn/problem/2969/

最新文章

热门文章