洛谷 1255. P1255 数楼梯
原题链接
简单
作者:
蓬蒿人
,
2024-02-18 17:16:34
,
所有人可见
,
阅读 31
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
// 注意要通过100%的数据的话就要 高精度计算
// 只要开三个vector数组存储 不断循环计算下去就好了
// 一个是当前值 另外是前一个位置的和前二个位置的
int n;
vector <int> a,b,ans;
vector <int> add(vector <int> &a,vector <int> &b) {//高精度模板
if (a.size()<b.size()) return add(b,a);
vector <int> sum;
int t=0;
for (int i=0;i<a.size();i++) {
t+=a[i];
if (i<b.size()) t+=b[i];
sum.push_back(t%10);
t/=10;
}
if (t) sum.push_back(t);
return sum;
}
int main () {
cin>>n;
if (n<=2) {//n<=2直接输出
cout<<n;
return 0;
}
a.push_back(1);
b.push_back(2);
for (int i=3;i<=n;i++) {
ans=add(b,a);
a=b;
b=ans;
}
//高精度计算是倒着存储的 如果要输出 反一下哦
for (int i=ans.size()-1;i>=0;i--) cout<<ans[i];
return 0;
}