ZeroJudge D712: The 3n + 1 problem

 題目敘述

本題採EOF方式收資料，每筆資料有兩個1~1000000的正整數A和B。要求輸出A和B還有「從A到B的3n+1 Problem的總Cycle次數最多的次數」。

3n+1:

如果N=1，return 1。

如果N是偶數，return N/2。

如果N是奇數，return 3N+1。

範例輸入 #1

1 10

100 200

201 210

900 1000

範例輸出 #1

1 10 20

100 200 125

201 210 89

900 1000 174

解題思路

本題可以用建立1到1000000的表來做，但是要跑1000000次的3N+1函式還是很耗時，可以發現當N可以被2整除時，他的3N+1函式回傳值就會是N/2的回傳值再加1，利用這點只需要判斷1到1000000中的奇數就好了。但是這樣子還是不夠快，所以除了將3N+1函式的回傳值進行建表，還需要進行A到B的最大值的線段數建立，最後再建立一個Query的函式將A到B的最大值進行計算，這樣子就不會TLE了。另外，測資中有可能A會大於B，這種情況就需要Swap(A, B)，但是輸出的時候還是要按照原有的順序進行輸出，這點需注意。

解題程式碼如下 (僅供參考)：

#include <iostream>
using namespace std;

int MAP[1000005] = {};
int a, b, maxx = -1;
int tree[3000000] = {};

void initial() {
    for(int i = 2; i < 1000001; i++)
    {
        long long int c = i;
        int count = 1;
        if(i % 2 == 0)
        {
            MAP[i] = MAP[i>>1]+1;
            continue;
        }
        while(c >= i)
        {
            if(c % 2)
            {
                c = c*3+1;
                c >>= 1;
                count+=2;
            }
            else
            {
                c = c>>1;
                count++;
            }
        }
        MAP[i] = count + MAP[c]-1;
    }
}

void build(int l, int r, int index)
{
    if (l == r)
    {
        tree[index] = MAP[l];
        return;
    }
    build(l, (l+r)/2, (2*index)+1);
    build(((l+r)/2)+1, r, (2*index)+2);
    tree[index] = max(tree[(index*2)+1], tree[(index*2)+2]);
    return;
}

void query (int l, int r, int index)
{
    if (a <= l && r <= b)
    {
        maxx = max(maxx, tree[index]);
        return;
    }
    if (l == r)
    {
        maxx = max(maxx, tree[index]);
        return;
    }
    int half = (l+r)/2;
    if (a <= half)
    {
        query(l, half, (index*2)+1);
    }
    if (b > half) query (half+1, r, (index*2)+2);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.sync_with_stdio(0);
    cout.tie(0);
    MAP[1] = 1;
    initial();
    build(1, 1000000, 0);
    while (cin >> a >> b)
    {
        int c = a;
        int d = b;
        if (a > b) swap(a, b);
        maxx = -1;
        query(1, 1000000, 0);
        cout << c << " " << d << " " << maxx << "\n";
    }
}