学步园

小记：真是坑的题目，我以为会有1-999999这样的数据。我用数组标记，每个循环过的数我就记下它的循环次数。下次碰到就直接输出。尼玛爆了RE。用暴力还直接AC了。

思路：暴力吧。我这个RE，大神们帮忙看看。。。

RE的：

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;

const int MAX_ = 3000010;

long long d[MAX_];

long long dfs(int x){
    if(d[x])return d[x];
    if(x == 1)return d[x] = 1;
    if(x%2){
        return d[x] = dfs(3*x + 1) + 1;
    }
    else {
        return d[x] = dfs(x/2) + 1;
    }
}

int main(){
    //freopen("f:\\out.txt","w",stdout);
    long long n,m, ans, T;

    while(cin>>n>>m){
        cout<<n<<" "<<m;
        if(n > m)swap(n,m);
        memset(d,0,sizeof(d));
        ans = -1;
        for(int i = n; i <= m; ++i){
            if(!d[i]){
                d[i] = dfs(i);
            }
            if(ans < d[i])ans = d[i];
        }
        cout<<" "<<ans<<endl;
    }

    return 0;
}

暴力的：

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;

int df(int x,int n){
    if(x == 1)return n;
    x = (x%2!=0)?(3*x+1):(x/2);
    return df(x,n+1);
}

int main(){
    //freopen("f:\\out.txt","w",stdout);
    long long n,m, ans, T;

    while(cin>>n>>m){
        cout<<n<<" "<<m;
        if(n > m)swap(n,m);
        ans = -1;
        for(int i = n; i <= m; ++i){
            T = df(i,1);
            if(ans < T)ans = T;
        }
        cout<<" "<<ans<<endl;
    }

    return 0;
}