luogu530225 @ 2022-01-25 16:16:09
#include<bits/stdc++.h>
using namespace std;
int main(){
string a,b,c;
int d[700]={0};
for(int i=0;i<=699;i++)d[i]=0;
cin>>a>>b;
int lena= a.length();
int lenb= b.length();
int len=max(lena,lenb);
for(int i=len-1;i>=0;i--){
if(a[i]>='0'&&a[i]<=('9'+9)&&b[i]>='0'&&b[i]<=('9'+9))c[i]=a[i]+b[i]-'0';
else if(a[i]>='0'&&a[i]<=('9'+9))c[i]=a[i];
else c[i]=b[i];
if(d[i]==1){
c[i]+=1;
}
if(c[i]>'9'){
c[i]-=10;
d[i-1]=1;
}
}
if(c[len]=='1'){
for(int i=0;i<=len;i++){
cout<<c[i];
}
}else for(int i=0;i<=len-1;i++){
cout<<c[i];
}
return 0;
}
by AFewSuns @ 2022-01-25 16:26:05
主页双帖,紫衫请
by EC75 @ 2022-01-25 16:46:02
@贾旭尧666 用Python
i=int(input())
a=1
b=1
c=1
x=3
mod=1000000009
while x<=i+1:
c=a+b
a=b
b=c
x=x+1
if i==0:
print(0)
else:
print(c)
by luogu530225 @ 2022-01-25 17:13:20
@AFewSuns ??
by Mandel520 @ 2022-01-25 20:20:02
写复杂了, 高精部分这样实现就可以了
#include<stdio.h>
int steps[5005][5005];
int n;
int main(){
scanf("%d", &n);
steps[1][1] = 1; //走上第一层有1种方案
steps[2][1] = 2; //走上第二层有2种方案
for (int i = 3; i <= n; i++){//高精度加法
for (int j = 1; j <= 5000; j++){
steps[i][j] += steps[i - 1][j] + steps[i - 2][j];//这一位的值是前面两行这一位的值之和(斐波那契)
steps[i][j] += steps[i][j - 1] / 10; //处理进位
steps[i][j - 1] %= 10; //处理进位
}
}
int ok = 0;
for (int i = 5000; i >= 1; i--) { //输出第n层的总方案数
if (steps[n][i]) ok = 1;
if (ok) printf("%d", steps[n][i]);
}
if (ok == 0) printf("0");
puts("");
return 0;
}
by juxiaodong @ 2022-02-05 22:39:09
@Jeremy_Mandel 当需要输出的数中间有0时,最后一个for循环是怎样判断是否输出0的?或者你能不能再解释解释从int ok;到末尾的算法实现?我还是不太理解怎样输出的
by Mandel520 @ 2022-02-06 12:03:41
@jxdasdfghjkl
例如, 存在数组steps[n]中的数是:
[0, 1, 0, 3, 0, 0]
最后一个for循环从后往前输出时:
首先遇到0, 此时ok = 0, 不输出
然后遇到0, 此时ok = 0, 不输出
然后遇到3, 因此ok变成1, 输出3
然后遇到0, 此时ok = 1, 输出0
然后遇到1, 此时ok = 1, 输出1
然后遇到0, 此时ok = 1, 输出0
因此最后输出结果为3010
总结: 一旦遇到第一个不为0的数, 后面的数都会输出, 所以数字中间的0也会输出
by juxiaodong @ 2022-02-06 19:26:12
@Jeremy_Mandel 明白了,谢谢
by Crybaby_ @ 2022-02-27 16:30:37
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <cmath>
#define MAXN 105
typedef long long ll;
using namespace std;
const int N = 101;
int step[5001][5001];
int main() {
int n;
scanf("%d", &n);
step[1][1] = 1;
step[1][0] = 1;
step[2][1] = 2;
step[2][0] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= step[i - 1][0]; j++) {
step[i][j + 1] += (step[i - 1][j] + step[i - 2][j] + step[i][j]) / 10;
step[i][j] = (step[i - 1][j] + step[i - 2][j] + step[i][j]) % 10;
}
if (step[i][step[i - 1][0] + 1] > 0) {
step[i][0] = step[i - 1][0] + 1;
} else {
step[i][0] = step[i - 1][0];
}
}
for (int i = step[n][0]; i > 0; i--) {
printf("%d", step[n][i]);
}
return 0;
}