C++ 高精模板

国王游戏

感谢洛谷贡献的题目，链接如下：
P1080 国王游戏
那题目到底讲了什么了，大概就是国王让自己和所有大臣左右手都写上一个数，然后排成一排，自己一定是第一个，每个大臣自己前面所有人左手的数乘积除自己右手的数作为获奖数。然后为怎么排列大臣可以让获奖最大的大臣获奖最小。
这题真是有趣神奇！

如何贪心？

贪心算法并不难，难的是证明。 — 杀某布基道斯基(shajima)
那这道题咋弄(⊙o⊙)?贪心的规则一定要可以转移，那先从简单情况入手。看下面：

此时国王后面只有两个大臣，那排列只有两种，对吧？
$$an{s}_1=max(a_0/b_1,a0\ast a1/b2)$$
$$an{s}_2=max(a_0/b_2,a_0\ast a_2/b_1)$$
显然这里有$a_0\ast a_2/b_1>a_0/b_1$和$a_0\ast a_1/b_2>a_0/b_2$，因此只要有：
$$a_0\ast a_2/b_1>a_0\ast a_1/b_2$$
即$a_1\ast b_1<a_2\ast b_2$就有$an{s}_1<an{s}_2$。所以神奇吧！为了取到最小值，需要把$a_i\ast b_i$小的放前面。并且这里由于交换两个大臣位置并不影响前面序列的最优情况，因此无后效性，贪心规则没问题。

代码展示

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int n, lens = 1, lenm = 1, lena = 1;
//sum乘积累加，maxn最大金币数，ans每个大臣获得金币数
int sum[10010] = {0, 1}, maxn[10010] = {0, 1}, ans[10010]; //第一位是位数

struct tmp
{
    long long l, r;
    bool operator < (const tmp x) const 
    {
            return l * r < x.l * x.r;
    }
}coin[1001];

void muti(long long x)
{
    int tmp = 0;
    for(int i = 1; i <= lens; i++)
        sum[i] *= x;
    for(int i = 1; i <= lens; i++)
    {
        tmp += sum[i];
        sum[i] = tmp %10;
        tmp /= 10;
    }
    while(tmp != 0)
    {
        lens++;
        sum[lens] = tmp % 10;
        tmp /= 10;
    }
}

void cut(long long x)
{
    memset(ans, 0, sizeof(ans));
    lena = lens;
    int tmp = 0;
    for(int i = lena; i >= 1; i--)
    {
        tmp *= 10;
        tmp += sum[i];
        if(tmp >= x)
        {
            ans[i] = tmp / x;
            tmp %= x;
        }
    }
    while(ans[lena] == 0)
    {
        if(lena == 1)
            break;
        lena--;
    }
}

void max()
{
    if(lena > lenm)
    {
        for(int i = 1; i <= lena; i++)
            maxn[i] = ans[i];
        lenm = lena;
    }
    else if(lena == lenm)
    {
        for(int i = lena; i >= 1; i--)
            if(maxn[i] < ans[i])
            {
                for(int j = 1; j <= lena; j++)
                    maxn[j] = ans[j];
                lenm = lena;
                break;
            }
    }
}

int main()
{
//  freopen("game.in", "r", stdin);
//  freopen("game.out", "w", stdout);
    cin >> n;
    cin >> coin[0].l >> coin[0].r;
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &coin[i].l, & coin[i].r);
    sort(coin + 1, coin + n + 1);
    for(int i = 1; i <= n; i++)
    {
        muti(coin[i - 1].l);
        cut(coin[i].r);
        max();
    }
    for(int i = lenm; i >= 1; i--)
        cout << maxn[i];
}

高精模板

1. 高精+高精

//c = a+b,a>=0,b>=0
#include<bits/stdc++.h>
using namespace std;
vector<int> add(vector<int> &a,vector<int> &b){
    if(a.size()<b.size()) return add(b,a); //这里注意将大的放在前面
    
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size();i++){
        t+=a[i];
        if(i<b.size()) t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t) c.push_back(t);
    return c;
}

按位相加，余10保留，除10进位，最后记得最后进的位也要保存。

2. 高精-高精

//c=a-b,满足a>=b,a>=0,b>=0
#include<bits/stdc++.h>
using namespace std;
vector<int> sub(vector<int> &a,vector<int> &b){
    vector<int> c;
    for(int i=0,t=0;i<a.size();i++){
        t=a[i]-t;
        if(i<b.size()) t-=b[i];
        c.push_back((t+10)%10);
        if(t<0) t=1; //不足往前借位
        else t=0;
    }
    while(c.size()>1 && c.back()==0) c.pop_back(); //去掉前置0
    return c;
}

3. 高精度乘低精度

// c=a*b,a>=0,b>0
//82*6 t=12 c={2} t=1->t=49 c={2,9} t=4->c={2,9,4} t=0->end
#include<bits/stdc++.h>
using namespace std;
vector<int> mul(vector<int> &a,int b){
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size() || t;i++){ //这里这个||t太精髓了吧，之后的位也保留进来
        if(i<a.size()) t+=a[i]*b;
        c.push_back(t%10); //除余保留
        t/=10; //进位
    }
    return c;
}

4. 高精度除以低精度

// a/b=c...r,a>=0,b>0
//98/5  r=9 c={1} r=4 -> r=48 c={1,9} r=3 -> end c={9,1} r=3
//37/5  r=3 c={0} r=3 -> r=37 c={0,7} r=2 -> end c={7,0} -> c={7} r=2;
#include<bits/stdc++.h>
using namespace std;
vector<int> div(vector<int> &a,int b,int &r){ //注意这里r是引用参数，可修改的
    vector<int> c;
    r=0; //余数
    for(int i=a.size()-1;i>=0;i--){
        r=r*10+a[i];
        c.push_back(r/b);
        r%=b;
    }
    reverse(c.begin(),c.end());
    while(c.size()>1 && c.back()==0)c.pop_back();//去掉前置0
    return c;
}

其他做法

我们知道python不需要申明数据类型，也就是说可以用来做高精度的乘法。那这道题也可以用Python求解偷懒！

N = int(input())
s = input().split()
S = int(s[0])
T = int(s[1])
a = []
for i in range(1, N + 1):
    k = input().split()
    a.append([int(k[0]), int(k[1])])
a.sort(key=lambda x: x[0]*x[1])
ans = 0
for i in range(0, N):
    if (S // (a[i])[1] > ans):
        ans = S // (a[i])[1]
    S *= (a[i])[0]
print(ans)

关于list自定义排序，可以查看下面这篇博客：

Python的自定义排序 以及两种排序方式