A60 正经题解

题意分析
汉诺塔问题，但是每个大小的圆盘都有两个且没有任何区别，求需要移动圆盘多少次才能完成它
解题思路
正常的汉诺塔每个大小只有一个圆盘，我们先从这个开始理解：
设$n$为大小种数，$f_i$为$n=i$时的最少次数：
$n=1$时，$f_1=1$。$n=2$时，$f_2=3$……这些数字是有规律的！通过观察可以得出$f_n=2^n-1$。
回到该问题，$n=1$时，$f_1=2$。$n=2$时，$f_2=6$……看起来不容易找到规律，但是如果观察前后项的关系，我们可以发现：
$2 \times 2 +2=6$，$6 \times2+2=14$，于是我们得出基础$70pts$解法（放在$AC$代码第二个）。
没有$AC$，观察数据范围，发现$n$可能达到$200$，至少要$200$位二进制才能承受的起$200$次的乘$2$，考虑高精度加法优化，得到第一个$AC$代码（$AC$代码第一个）。
虽然已经$0$毫秒了，且该代码在数据范围内已十分接近最优，但是为了水字数尊重一下这道题，我还是希望有神人能写快速幂之类的优化，公式放在这了，$f_n=2^{n+1}-2$，有优化方案的自取。

AC代码
$100pts$高精度加法递推：

#include <bits/stdc++.h>
using namespace std;
string ans="2";

string add(string a, string b){
    int sa = a.size(), sb = b.size();
    bool flag=false;
    if(sa<sb) swap(a, b);
    for(int i=1;i<=sb;++i){
        int o1 = a[sa-i]-'0', o2 = b[sb-i]-'0';
        a[sa-i] = (o1+o2+flag)%10+'0';
        if(o1+o2+flag>9)
            flag = true;
        else
            flag = false;
    }
    if(flag){
        for(int i=sb+1;i<=sa&&flag;++i){
            int o1 = a[sa-i]-'0';
            a[sa-i] = (o1+flag)%10+'0';
            if(o1+flag>9)
                flag = true;
            else
                flag = false;
        }
        if(flag) a = "1"+a;
        
    }
    return a;
}

int main(){
    int n;
    cin >> n;
    for(int i=1;i<n;++i){
        ans = add(add(ans, ans), "2");
    }
    cout << ans;

    return 0;
}

$70pts$无高精度递推:

#include <bits/stdc++.h>
using namespace std;
long long ans=2;

int main(){
    int n;
    cin >> n;
    for(int i=1;i<n;++i){
        ans=ans*2+2;
    }
    cout << ans;

    return 0;
}