POJ 1207 The 3n + 1 problem
来源：程序员人生 发布时间：2014-09-25 04:22:50 阅读次数：1914次
水题，直接筛一下就好。不过需要注意输出。
自己学校的渣OJ 的数据范围才叫大：All integers will be less than 10,000,000 and greater than 0.
跑了1.7ms。时限2ms。
POJ这道题数据范围是：All integers will be less than 10,000 and greater than 0.
直接所有的删掉2个0。直接就0ms了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
bool v[100001];
int a[100001];
queue<int>q;
int bfs()
{
memset(v,0,sizeof(v));
memset(a,0,sizeof(a));
q.push(1);v[1]=1,a[1]=1;
while(1)
{
int i,tmp,ans;
bool ok=0;
while(!q.empty())
{
tmp=q.front(),q.pop();
if((tmp-1)%3==0&&tmp>1&&((tmp-1)/3)&1)
{
ans=(tmp-1)/3;
if(!v[ans]&&ans<100001)
v[ans]=1,a[ans]=a[tmp]+1,q.push(ans),ok=1;
}
ans=tmp*2;
if(!v[ans]&&ans<100001)
v[ans]=1,a[ans]=a[tmp]+1,q.push(ans),ok=1;
}
if(!ok)break;
}
long long i,ans,tmp;
for(i=1;i<100001;i++)
{
if(!v[i])
{
tmp=i;ans=0;
while(1)
{
if(tmp&1)
tmp=3*tmp+1,ans++;
else
tmp/=2,ans++;
if(tmp<100001&&a[tmp]!=0)break;
}
a[i]=a[tmp]+ans;
v[i]=1;
}
}
}
int main()
{
int a1,a2,i,tmp;
bfs();
while(~scanf("%d%d",&a1,&a2))
{
bool ok=0;
if(a1>a2)ok=1;
tmp=max(a1,a2);
a1=min(a1,a2),a2=tmp;
tmp=0;
for(i=a1;i<=a2;i++)
tmp=max(tmp,a[i]);
if(!ok)
printf("%d %d %d
",a1,a2,tmp);
else
printf("%d %d %d
",a2,a1,tmp);
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
