大数计算模板---zoj_3447

        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;
}