Posted on 2011-12-03 13:09
C小加 阅读(1592)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
NYOJ地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=271
题意：
给出一个区间，求区间内每一个数按规则（奇数取3n+1，偶数取n/2）变换最后变成1的步数，求最大的一个步数。
思路：
这道题在poj上很快就是水过了，用的是一般的笨方法，后来看到学校的oj也有这道题，就复制粘贴过去，结果WA了，好诡异。然后改了一些细节，TLE了，顿时无语。然后经过各种优化啊，记忆优化啊，有木有！！优化到不能再优化啊，还是TLE啊。没办法了，只能试试其他的方法了。很简单就能想到打表，把题目要求的数据范围内所有的步数都求出来，然后就可以顺利的水了，水过后看见别人做的，用记忆的过了啊，有木有！！我怎么就没过呢~~更多的还是打表~~我的时间有点慢，不解释。。。。顺便说一下，这道题还是很阴险的，做的时候要细心呀。。。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int d[10003];
int main()
{
//freopen("input.txt","r",stdin);
int i,j,t;
memset(d,0,sizeof(d));
for(int k=2;k<10003;k++)//打表
{
t=k;
while(1!=t)
{
if(t&1)
{
t=t*3+1;
}
else t>>=1;
d[k]++;
}
}
while(cin>>i>>j)
{
int max=0,t=0;
cout<<i<<" "<<j<<" ";
if(i>j)
{
i^=j;j^=i;i^=j;
}
for(int k=i;k<=j;k++)
{
if(max<d[k])
max=d[k];
}
cout<<max+1<<endl;
}
return 0;
}