P1096 题解 - 洛谷保存站

### 本蒟蒻（小升初）第一次写题解，如有问题请见谅。

[题目传送门](https://www.luogu.com.cn/problem/P1096)

本题解介绍一种新的做法（使用递归，直接在字符串上操作）

### 题目大意

此题是小奥的改编题。

在小奥中，我们学过，如果将题中的 $2n$ 个圆盘改为 $n$ 个的话，最小的移动次数为 $2^n-1$。

在这题中，因为每个尺寸都有两个相同的圆盘，所以答案为小奥原题的两倍(即 ${2}^{n+1}-2$)。

首先上一个部分分的代码。

```cpp
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,t;
int main(){
    cin>>n;
    t=(1<<n+1)-2;
    cout<<t;
    return 0;
}
```

然后喜提 $50$ 分。

这个题数据量很大，无法使用 unsigned long long。

大部分大佬们使用数组和字符串存储。

~~我直接对字符串进行操作~~。

### 代码细节

首先，我们需要计算 $2$ 的 $n+1$ 次方，用字符串的话，字符串最开始应为 `2`(当然为 `1` 也行)，这里可以用递归，也可以循环。

然后将字符串最后一位减 $2$ 即可,因为 $2$ 的 $n+1$ 次方末尾必然大于 $2$,这也是小奥中学过的。

先贴上标准的错误代码:

```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
string solve(string t,int len){
    if(len==n+1) return t;
    //边界返回。
    for(int i=t.size()-1;i>0;i--){
        int a=int(t[i]);
        //此处应加入一些东西。
        a*=2;
        a-=48;
        if(a>57){
            a-=10;
            int k=t[i-1];
            k++;
            //此处是错误的根本，进位会被算2次。
            t[i-1]=char(k);
        }
        t[i]=char(a);
    }
    int b=int(t[0]);
    b*=2;b-=48;
    //此处应加入一些东西
    if(b>57){
        b-=10;
        t="1"+t;
        t[1]=char(b);
    }else{
        t[0]=char(b);
    }
    //为何把此单独计算？因为数组会越界。
    return solve(t,len+1);
    //递归求下一步答案。
}
int main(){
    cin>>n;
    string s=solve("2",1);
    int k=int(s[s.size()-1]);
    k-=2;s[s.size()-1]=char(k);
    cout<<s<<endl;
    return 0;
}
```
然后喜提 $10$ 分（估计是样例）。

请注意进位要在乘以二之后进位，这是一个易错点，也是程序的关键之一。在此我们使用 $pos$ 变量检查。

接下来贴上AC代码（建议不要直接复制）。

```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
string solve(string t,int len){
    bool pos=false;
    //pos是处理进位的关键。
    if(len==n+1) return t;
    //边界返回。
    for(int i=t.size()-1;i>0;i--){
        int a=int(t[i]);
        a*=2;
        if(pos) a++;
        //上一位进位
        pos=false;
        a-=48;
        if(a>57){
            a-=10;
            int k=t[i-1];
            pos=true;
            //pos为true代表有进位。
            t[i-1]=char(k);
        }
        t[i]=char(a);
    }
    int b=int(t[0]);
    b*=2;b-=48;
    if(pos){
        b++;
    }
    //注意此处还要处理进位。
    if(b>57){
        b-=10;
        t="1"+t;
        //乘以两倍，进位最多加一。
        t[1]=char(b);
        //原最高位位数已挪动。
    }else{
        t[0]=char(b);
    }
    //为何把此单独计算？因为数组会越界。
    return solve(t,len+1);
    //递归求下一步
}
int main(){
    cin>>n;
    string s=solve("2",1);
    int k=int(s[s.size()-1]);
    k-=2;s[s.size()-1]=char(k);
    cout<<s<<endl;
    return 0;
}
```

正在渲染内容...