Hanoi 双塔问题·题解

思路：
普通的汉诺塔是 $1$ 层 $1$ 次， $2$ 层 $3$ 次， $3$ 层 $7$ 次，可以看得出 $n$ 层是 $2^n-1$ 次。当然这道题是双塔，所以1乘二就行，注意因为 $1 \leq n \leq 200$ ，所以要高精度。我是不会说我是直接拿以前自己写的模版的。
错误代码示范：WA*3

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

long long n,num=1;

int main(){
    cin>>n;
    for(int i=0;i<n;i++) num*=2;
    num--,num*=2;
    cout<<num;
}

正确代码：

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

bool strnumcmp(string s1,string s2){
    int u=s1.length(),v=s2.length();
    if(u!=v) return u>v;
    for(int i=0;i<u;i++) if(s1[i]!=s2[i]) return s1[i]>s2[i];
    return true;
}

string bigintsub(string a,string b){
	int length=max(a.length(),b.length());
	bool flag=0,flag2=0;
	if(strnumcmp(b,a)) swap(a,b),flag=1;
	int nums[length+5]={0};
	int l=0;
	for(int i=a.length()-1;i>=0;i--) nums[l++]+=a[i]-'0';
	l=0;
	for(int i=b.length()-1;i>=0;i--) nums[l++]-=b[i]-'0';
	for(int i=0;i<length;i++){
		if(nums[i]<0) nums[i]+=10,nums[i+1]--;
	}
	string num=""; 
	if(flag==1) num="-";
	for(int i=length-1;i>=0;i--) if(nums[i]!=0 || flag2==1) num+=(nums[i]+'0'),flag2=1;
	return num;
}

string bigintmul(string a,int b){
	int length=a.length();
	int nums[length+100]={0};
	int l=0;
	for(int i=a.length()-1;i>=0;i--) nums[l++]+=a[i]-'0';
	for(int i=0;i<length;i++){
		nums[i]*=b;
	}
	for(int i=0;i<length;i++){
		if(nums[i]/10>=1) nums[i+1]+=nums[i]/10,nums[i]%=10,length++;
	}
	string num="";
	for(int i=length-1;i>=0;i--) num+=(nums[i]+'0');
	return num;
}

string a="1";
int n;

int main(){
	cin>>n;
	for(int i=0;i<=n;i++) a=bigintmul(a,2);
	a=bigintsub(a,"2");
	cout<<a;
}