大数计算模板---zoj_3447
- 博客分类:
- c++基础
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4190
很多DP,贪心会涉及高精度,苦于不会JAVA和PY等,只能找了个大数计算的模板,先膜拜在学习。这个代码请参考:
http://www.cppblog.com/patriking/archive/2011/01/09/138137.html
这道题贪心。结果最大的策略就是:不断最小的两个数,计算后放回数集之中;相反的,结果最小的策略就是:不断取出K个(如果不足则取出全部)最大的数,计算后放回数集之中。题目结果很大,需要高精度。
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iterator>
#include<string.h>
using namespace std;
const int MAXN = 102;
class bigInt
{
public:
int num[302], len;
bigInt() { num[0] = 0, len = 0; }
bigInt operator=(const int &a)
{
int tmp = a;
len = 0;
while (tmp)
num[len++] = tmp % 10, tmp /= 10;
if (!len) num[0] = 0, len = 1;
}
bigInt(const int &a)
{
int tmp = a;
len = 0;
while (tmp)
num[len++] = tmp % 10, tmp /= 10;
if (!len) num[0] = 0, len = 1;
}
bool operator<(const bigInt &a)
{
if (a.len != len)
return len < a.len;
for (int i = len - 1; i >= 0; i--)
if (num[i] != a.num[i])
return num[i] < a.num[i];
return false;
}
bigInt operator+(const bigInt &a)
{
bigInt res;
int i, j, c = 0, adda, addb;
for (i = 0, j = 0; i < len || j < a.len || c; )
{
adda = 0, addb = 0;
if (i < len)
adda = num[i++];
if (j < a.len)
addb = a.num[j++];
res.num[res.len++] = (adda + addb + c) % 10;
c = (adda + addb + c) / 10;
}
return res;
}
bigInt operator-(const bigInt &b)
{
bigInt res;
int i, j, c = 0, suba, subb;
for (i = 0, j = 0; i < len || j < b.len || c; )
{
suba = 0, subb = 0;
if (i < len)
suba = num[i++];
if (j < b.len)
subb = b.num[j++];
res.num[res.len++] = (suba - subb + c + 10) % 10;
c = (suba - subb + c + 10) / 10 - 1;
}
for (i = res.len - 1; i > 0; i--)
if (res.num[i]) break;
res.len = i + 1;
return res;
}
bigInt operator*(const bigInt &b)
{
bigInt res;
int i, j, c, now, mulb, tmp;
memset(res.num, 0, sizeof(int) * (len + b.len));
for (i = 0; i < len; i++)
{
now = i, c = 0;
for (j = 0; j < b.len || c; )
{
mulb = 0;
if (j < b.len)
mulb = b.num[j++];
tmp = res.num[now] + num[i] * mulb + c;
res.num[now++] = tmp % 10;
c = tmp / 10;
}
}
for (i = len + b.len - 1; i > 0; i--)
if (res.num[i]) break;
res.len = i + 1;
return res;
}
bigInt operator/(const bigInt &b)
{
bigInt res, diva;
int i, j, c;
for (i = len - 1; i >= 0; i--)
{
if (diva.len > 1 || diva.num[0])
{
for (j = diva.len - 1; j >= 0; j--)
diva.num[j + 1] = diva.num[j];
diva.len++;
}
diva.num[0] = num[i];
if (!diva.len) diva.len = 1;
res.num[i] = 0;
while (!(diva < b))
diva = diva - b, res.num[i]++;
}
for (i = len - 1; i > 0; i--)
if (res.num[i]) break;
res.len = i + 1;
return res;
}
bigInt operator%(const bigInt &b)
{
bigInt res, diva;
int i, j, c;
for (i = len - 1; i >= 0; i--)
{
if (diva.len > 1 || diva.num[0])
{
for (j = diva.len - 1; j >= 0; j--)
diva.num[j + 1] = diva.num[j];
diva.len++;
}
diva.num[0] = num[i];
if (!diva.len) diva.len = 1;
res.num[i] = 0;
while (!(diva < b))
diva = diva - b, res.num[i]++;
}
for (i = diva.len - 1; i > 0; i--)
if (diva.num[i]) break;
diva.len = i + 1;
return diva;
}
void display()
{
int i;
for (i = len - 1; i > 1; i--)
if (num[i]) break;
for (; i >= 0; i--)
printf("%d", num[i]);
printf("\n");
}
};
bool cmp(bigInt a, bigInt b)
{
return (b<a);
}
bool cmp1(bigInt a, bigInt b)
{
return (a<b);
}
int main()
{
int x, n, k;
vector<bigInt>v;
vector<bigInt>t;
vector<bigInt>tmp;
bigInt tmpx;
freopen("e:\\zoj\\zoj_3447.txt","r",stdin);
while(scanf("%d%d",&n,&k)!=EOF)
{
v.clear();
t.clear();
for(int i = 0; i < n; i++)
{
scanf("%d",&x);
bigInt tmp_x = x;
v.push_back(tmp_x);
}
copy(v.begin(),v.end(),back_inserter(t));
while(v.size()>1)
{
tmp.clear();
sort(v.begin(),v.end(),cmp);
if(v.size()> k){
for(int i = k; i < v.size(); i++){
tmp.push_back(v[i]);
}
tmpx = 1;
for(int i = 0; i < k; i++){
tmpx = tmpx * v[i];
}
tmpx = tmpx + 1;
tmp.push_back(tmpx);
v.swap(tmp);
}else{
tmpx = 1;
for(int i = 0; i < v.size(); i++)
tmpx = tmpx * v[i];
tmpx = tmpx + 1;
tmp.push_back(tmpx);
v.swap(tmp);
}
}
while(t.size()>1)
{
tmp.clear();
sort(t.begin(),t.end(),cmp1);
if(t.size()>2){
for(int i = 2; i < t.size(); i++){
tmp.push_back(t[i]);
}
tmpx = 1;
for(int i = 0; i < 2; i++){
tmpx = tmpx*t[i];
}
tmpx = tmpx + 1;
tmp.push_back(tmpx);
t.swap(tmp);
}else{
tmpx = 1;
for(int i = 0; i < t.size(); i++)
tmpx = tmpx * t[i];
tmpx = tmpx + 1;
tmp.push_back(tmpx);
t.swap(tmp);
}
}
tmpx = t[0]-v[0];
tmpx.display();
}
return 0;
}
发表评论
-
struct数据对齐与#pragma pack(n)
2011-09-14 16:38 1100对struct数据对齐与#pragma pac ... -
位图bitmap
2011-07-13 21:08 916bitmap是一种广泛使用的数据结构,主要用在 ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2841zoj_2243笛卡 ... -
中缀表达式的转化---zoj_2483,zoj_3025
2011-07-04 18:54 1142在我们的日常生活中,中缀表达式是最常用的计算表达方式 ... -
STL---priority_queue zoj_2212,zoj_2724,zoj_3230
2011-06-28 17:50 1265priority_queue顾名思意是优先 ... -
STL---sort
2011-06-25 16:39 808引用:http://blog.csdn.net/rattl ... -
float,double范围和精度
2011-06-23 15:55 1447今天遇到一题zoj_1128,数据范围是(0 ... -
STL map的使用---zoj_2832,zoj_1899,zoj_3023
2011-06-10 15:40 1117map是一类关联式容器。它的特点是增加和删除节 ... -
C++字符串输入操作
2011-06-10 15:34 3906问题1:输入为一行字符串被中间被一些空格隔开 ... -
C++带默认形参的函数
2011-05-22 22:46 1975先上代码: int sub(int x=8,int y=3 ... -
百度面试归~~我还是太年轻了。。。。
2011-05-10 16:24 1313一大早还没怎么睡醒就打了辆车去酒店面试,到了9点,我被带 ... -
const与指针
2011-05-06 20:54 712const 使用情况分类详析 const 用于指针的两种 ... -
指针,数组,sizeof
2011-05-06 17:02 854最近要百度面试,压力有点大。。。复习一下 已知 char *s ... -
c++创建对象,堆,栈。。。
2010-10-22 16:47 1344今天写作业 ,想通过写一个函数createLine来创建一条直 ... -
struct内存分配
2010-10-11 21:14 1244百度的笔试题 struct s1 { char ch, ... -
java,C++栈和堆
2010-09-30 19:04 1313额,看惯了java,最近看c++就是蛋疼。。。写 ...
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj4041正确题解源代码,以及运行程序
浙江大学ZOJ源码题解,按照题目类型和难易分类。
acm中zoj1002的可运行C++程序
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
一个非常非常非常非常实用的zoj结题代码
zoj的代码实现,很好,而且很全面,全部实现。
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
浙大acm OJ1204,自己做的,已经AC 分享一下,若有更好的算法可以教教我
能AC 通过的c++代码,包括zoj1002,1091,1789
浙江大学zoj题目代码,大量水题代码,齐全
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告