CSP历年复赛题-P1096 [NOIP2007 普及组] Hanoi 双塔问题

原题链接：https://www.luogu.com.cn/problem/P1096

题意解读：汉诺双塔的移动次数，与经典汉诺塔的区间在于同一个尺寸盘子有两个。

解题思路：

可以直接用经典汉诺塔方法来计算，双塔的结果就最终乘以2即可。

首先想到的是递归，但是由于数据量n最大200，递归会超时，但是50%的样例应该没问题，先拿分！

50分代码：

#include <bits/stdc++.h>
using namespace std;

int ans;

void hanoi(int n)
{
    if(n == 1)
    {
        ans++; //只剩一个盘子，移动到目标柱子
        return;
    }
    hanoi(n-1); //移动前n-1个盘子都暂存柱子
    ans++; //移动第n个到目标柱子
    hanoi(n-1); //移动前n-1个到目标柱子
}

int main()
{
    int n;
    cin >> n;
    hanoi(n);
    cout << ans * 2; //双塔乘以2

    return 0;
}

根据提示，考虑采用递推，直接借助上面递归代码运行出

n = 1，输出2

n = 2，输出6

n = 3，输出14

n = 4，输出30

n = 5，输出62

我们观察一下2,6,14,30,62，可以推出递推式f[n] = f[n-1] * 2 + 2，初始值f[1] = 2，最终结果是f[n]

由于n最大是200,2^200用long long也无法存储，需要高精度

先写出以下代码，再替换高精度

70分代码：

#include <bits/stdc++.h>
using namespace std;

long long f[205];

int main()
{
    int n;
    cin >> n;
    f[1] = 2;
    for(int i = 2; i <= n; i++)
    {
        f[i] = f[i-1] * 2 + 2;
    }
    cout << f[n];

    return 0;
}

加上高精度，只需要加法即可！

100分代码：

#include <bits/stdc++.h>
using namespace std;

vector<int> f[205];
vector<int> g2(1, 2); //高精度的2

vector<int> add(vector<int> &a, vector<int> &b)
{
    vector<int> res;
    int t = 0;
    int len = max(a.size(), b.size());
    for(int i = 0; i < len; i++)
    {
        if(i < a.size()) t += a[i];
        if(i < b.size()) t += b[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if(t) res.push_back(t);
    return res;
}

int main()
{
    int n;
    cin >> n;
    f[1] = g2;
    for(int i = 2; i <= n; i++)
    {
        vector<int> res = add(f[i-1], f[i-1]);
        f[i] = add(res, g2);
    }
    
    for(int i = f[n].size() - 1; i >= 0; i--) cout << f[n][i];

    return 0;
}