从杭电第一题开始A，发现做到1002就不会了，经过几天时间终于A出来了，顺便整理了一下关于大数的东西
其实这是刘汝佳老师在《算法竞赛 经典入门 第二版》 中所讲的模板，代码原封不动写上的，但是经过自己的使用与调试也明白了其中的内涵。
首先定义大数的结构体：
struct BigNum{
static const int BASE=;
static const int WIDTH=;
vector<int> s;
BigNum(long long num=){ *this=num; }
BigNum operator = (long long num){
s.clear(); //vector.clear() 移除容器中的元素
do{
s.push_back(num%BASE); //vectro.push_back() 向尾部添加元素
num/=BASE;
}while(num>);
return *this;
}
BigNum operator =(const string& str){
s.clear();
int x,len=(str.length()-)/WIDTH+;
int mmm=str.length();
for(int i=;i<len;i++){
int end=str.length()-i*WIDTH;
int start=max(,end-WIDTH);
sscanf(str.substr(start,end-start).c_str(),"%d",&x);
s.push_back(x);
/*
*sscanf(str.substr(start,end-start).c_str(),"%d",&x)
*
*sscanf(a,b,c);
*三个参数 将a中的字符串以b的格式写入到c中
*
*c_str() 据说是为了和C语言兼容，并不懂，有大神知道还请讲解
*
*substr() 复制
*/
}
return *this;
}
在定义的结构体中，可以将一个大数以字符串的形式输入到结构体BigNum 中的 vector容器中，WIDTH的作用是将这个大数字符串分割成八个字符。
并且在结构体中重载了赋值运算符"="然后就可以像 BigNum a="1122334455667789891484684689" 这样对a进行赋值。
然后重载输入输出流运算符：
ostream& operator << (ostream &out,const BigNum& x){
out<<x.s.back(); //vector.back() 回传最后一个数据
for(int i=x.s.size()-;i>=;i--){
char buf[];
sprintf(buf,"%08d",x.s[i]);
for(int j=;j<strlen(buf);j++)
out<<buf[j];
/*
*sprintf(a,b,c) 把c中的b格式的数据写入到a中
*/
}
return out;
}
istream& operator >>(istream &in,BigNum& x){
string s;
if(!(in>>s)) return in;
x=s;
return in;
}
重载之后，就可以使用 cin>>a; cout<<a; 进行输入输出。
ps:buf的大小是依据题目中的数据的大小而规定的。
重载 "+":
BigNum operator +(const BigNum& b) const{
BigNum c;
c.s.clear();
for(int i=,g=;;i++){
if(g==&&i>=s.size()&&i>=b.s.size()) break;
int x=g;
if(i<s.size()) x+=s[i];
if(i<b.s.size()) x+=b.s[i];
c.s.push_back(x%BASE);
g=x/BASE;
}
return c;
}
附上完整代码：
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
struct BigNum{
static const int BASE=;
static const int WIDTH=;
vector<int> s;
BigNum(long long num=){ *this=num; }
BigNum operator = (long long num){
s.clear(); //vector.clear() 移除容器中的元素
do{
s.push_back(num%BASE); //vectro.push_back() 向尾部添加元素
num/=BASE;
}while(num>);
return *this;
}
BigNum operator =(const string& str){
s.clear();
int x,len=(str.length()-)/WIDTH+;
int mmm=str.length();
for(int i=;i<len;i++){
int end=str.length()-i*WIDTH;
int start=max(,end-WIDTH);
sscanf(str.substr(start,end-start).c_str(),"%d",&x);
s.push_back(x);
/*
*sscanf(str.substr(start,end-start).c_str(),"%d",&x)
*
*sscanf(a,b,c);
*三个参数 将a中的字符串以b的格式写入到c中
*
*c_str() 据说是为了和C语言兼容，并不懂，有大神知道还请讲解
*
*substr() 复制
*/
}
return *this;
}
BigNum operator +(const BigNum& b) const{
BigNum c;
c.s.clear();
for(int i=,g=;;i++){
if(g==&&i>=s.size()&&i>=b.s.size()) break;
int x=g;
if(i<s.size()) x+=s[i];
if(i<b.s.size()) x+=b.s[i];
c.s.push_back(x%BASE);
g=x/BASE;
}
return c;
}
friend ostream& operator << (ostream &out,const BigNum& x);
friend istream& operator >>(istream &in,BigNum& x);
};
ostream& operator << (ostream &out,const BigNum& x){
out<<x.s.back(); //vector.back() 回传最后一个数据
for(int i=x.s.size()-;i>=;i--){
char buf[];
sprintf(buf,"%08d",x.s[i]);
for(int j=;j<strlen(buf);j++)
out<<buf[j];
/*
*sprintf(a,b,c) 把c中的b格式的数据写入到a中
*/ }
return out;
}
istream& operator >>(istream &in,BigNum& x){
string s;
if(!(in>>s)) return in;
x=s;
return in;
}
BigNum a,b,c;
string A,B;
int main(){
int T;
cin>>T;
int flag=;
while(T--){
//cin>>A>>B;
cin>>a>>b;
//a=A;
//b=B;
c=a+b;
cout<<"Case "<<flag<<":";
cout<<endl;
//cout<<A<<" "<<"+"<<" "<<B<<" = ";
cout<<a<<" "<<"+"<<" "<<b<<" = ";
if(T!=) cout<<c<<endl;
else cout<<c;
cout<<endl;
flag++;
}
return ;
}
ps：杭电对输出格式的控制真恐怖！！！