- POJ 2602 - Superlong sums
- Time: 1000MS
- Memory: 65536K
- 难度: 初级
- 分类: 高精度算法
0x00 POJ 原题
Description
The creators of a new programming language D++ have found out that whatever limit for SuperLongInt type they make, sometimes programmers need to operate even larger numbers. A limit of 1000 digits is so small… You have to find the sum of two numbers with maximal size of 1.000.000 digits.
Input
The first line of an input file contains a single number N (1<=N<=1000000) - the length of the integers (in order to make their lengths equal, some leading zeroes can be added). It is followed by these integers written in columns. That is, the next N lines contain two digits each, divided by a space. Each of the two given integers is not less than 1, and the length of their sum does not exceed N.
Output
Output file should contain exactly N digits in a single line representing the sum of these two integers.
Sample Input
4
0 4
4 2
6 8
3 7
Sample Output
4750
Hint
Huge input,scanf is recommended.
Source
Ural State University collegiate programming contest 2000
0x10 解题思路
非常恶心的大数相加
首先输入就够恶心了…哪有人逐位还要间断输入两个数的…
注意:
- 如果用
char[]保存加数和被加数,要用getchar()输入, - 如果用
int[]保存加数和被加数,要用scanf()输入。 - 用 cin 会超时,
cin是重载函数,没有指定格式,输入时比较浪费时间 - 100W 的空间不能局部静态申请,单可以全局静态申请,也可以局部动态申请(用
new)
最恶心得是,我把结果开头的 0(如果有的话)删去,竟然 WA…!
Output file should contain exactly N digits in a single line representing the sum of these two integers.
这是输出要求的格式,竟然要求 被加数、加数、和 的位数一致!!
按这样理解,这题是不允许最高位出现进位的…!!
0x20 AC 源码
0x21 解题方法一:使用 char[] 存储数字
//Memory Time
//11972K 1594MS
#include<iostream>
#include<string>
using namespace std;
const int size=1000000; //大数位数上限
int n; //大数位数
int a[size+1];
int b[size+1];
void add(char* A,char* B,char* ans)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int pa=0,pb=0;
int lena=strlen(A);
int lenb=strlen(B);
/*倒序*/
for(int i=lena-1;i>=0;i--)
a[pa++]=A[i]-'0';
for(int j=lenb-1;j>=0;j--)
b[pb++]=B[j]-'0';
int len=lena>lenb?lena:lenb;
char* c=new char[len+1]; //倒序的ans
int w=0; //低位到高位的进位
for(int k=0;k<len;k++)
{
int temp=a[k]+b[k]+w;
c[k]=temp%10+'0';
w=temp/10;
}
len--;
for(w=0;len>=0;len--) //w和len均作指针使用,已无意义
ans[w++]=c[len];
ans[w]='\0';
delete c;
return;
}
char A[size+1];
char B[size+1];
char ans[size+1];
int main(int i)
{
while(cin>>n)
{
getchar();
for(i=0;i<n;i++)
{
A[i]=getchar();
getchar(); //空格
B[i]=getchar();
getchar(); //回车
}
A[i]=B[i]='\0';
add(A,B,ans);
cout<<ans<<endl;
}
return 0;
}
0x22 解题方法二:使用 int[] 存储数字
//Memory Time
//17868K 1625MS
#include<iostream>
using namespace std;
int n; //大数位数
void add(int* a,int* b,char* ans)
{
char* c=new char[n+1]; //倒序的ans
int w=0; //低位到高位的进位
for(int k=0;k<n;k++)
{
int temp=a[k]+b[k]+w;
c[k]=temp%10+'0';
w=temp/10;
}
n--;
for(w=0;n>=0;n--) //w和n均作指针使用,已无意义
ans[w++]=c[n];
ans[w]='\0';
delete c;
return;
}
int main(int i)
{
while(cin>>n)
{
int* a=new int[n+1];
int* b=new int[n+1];
int* ta=new int[n+1];
int* tb=new int[n+1];
char* ans=new char[n+1];
for(i=0;i<n;i++)
scanf("%d %d",&ta[i],&tb[i]);
/*倒序*/
int pa=0,pb=0;
for(i=n-1;i>=0;i--)
{
a[pa++]=ta[i];
b[pb++]=tb[i];
}
add(a,b,ans);
cout<<ans<<endl;
delete a;
delete b;
delete ta;
delete tb;
delete ans;
}
return 0;
}