nyoj 114某种排序(水 大数+优化大数)
发布时间:2020-12-14 02:38:51 所属栏目:大数据 来源:网络整理
导读:某种序列 时间限制: 3000 ms ?|? 内存限制: 65535 KB 难度: 4 描述 数列A满足An = An-1 + An-2 + An-3,n = 3? 编写程序,给定A0,A1 和 A2,计算A99 输入 输入包含多行数据 每行数据包含3个整数A0,A1,A2 (0 = A0,A2 = 100000000) 数据以EOF结束 输出 对于输
某种序列
时间限制:
3000 ms ?|? 内存限制:
65535 KB
难度:
4
上传者 思路 : (水) 每个位置上存储一个长度为1的数 时间 44 内存 640 #include<bits/stdc++.h> using namespace std; #define mem(a) memset(a,sizeof(a)) int A,B,C; int a[100][1000]; //int b[1000],c[1000],d[1000],sum[1000]; void Save(int n,int *a){ int i=0; while(n) { a[i++]=n%10; n/=10; } } void add(int *b,int *c,int *d,int *sum) { int up=0; int t; for(int i=0;i<=999;i++) { t=b[i]+c[i]+d[i]+up; sum[i]=t%10; up=t/10; } } int main() { while(~scanf("%d%d%d",&A,&B,&C)) { if(!A && !B && !C) { printf("0n"); continue; } mem(a); Save(A,a[0]); Save(B,a[1]); Save(C,a[2]); for(int i=3;i<=99;i++) { add(a[i-1],a[i-2],a[i-3],a[i]); } int i=999; while(a[99][i]==0) i--; for(int j = i; j >= 0; j--) { printf("%d",a[99][j]); } printf("n"); } } 优化思路: 每个单位上存放一个长度为 7的数 time: 0 内存 :232 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int A,C; int a[100][100]; while(~scanf("%d%d%d",&C)) { int len=1; int up=0; memset(a,sizeof(a)); a[0][0]=A; a[1][0]=B; a[2][0]=C; for(int i = 3;i < 100; i++) { for(int j = 0;j < len; j++) { int ret = a[i-1][j] + a[i-2][j] + a[i-3][j] + up; a[i][j] = ret % 10000000; up = ret / 10000000; } if(up) { a[i][len++] = up; up = 0; } } printf("%d",a[99][len-1]); for(int i = len-2; i>=0; i--) printf("%07d",a[99][i]); printf("n"); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |