备战校赛（2）

知识点整理（2）高精

本次介绍的知识点是应对特定数据范围的一些方法

高精

高精度，顾名思义是用于解决输入数字位数过大而超出int乃至longlong范围的一种方法，下面将逐一举例。

高精加法

原题链接：洛谷P1601A+Bproblem（其实就是A+B问题的高精版本

解题方法：本题思路没啥好说的，就是A+B，下面主要讲如何实现高精加法，其实就是用一个数组来存储一个数，两个数相加即是让对应数位相加，然后进行进位操作，相加后便使进1，即让下一数位加一，然后本数位对10取余。

代码实现：

#include<iostream>
#include<string>
using namespace std;
int main(){
    string a, b;
    cin >> a >> b;
    int len = a.length() > b.length() ? a.length() : b.length();
    int a1[len + 10]{0}, b1[len + 10]{0};
    for (int i = a.length()-1,j=0; i >=0;i--,j++){
        a1[j] = a[i] - '0';
    }
    for (int i = b.length()-1,j=0; i >=0 ;i--,j++){
        b1[j] = b[i] - '0';
    }
    int c[len + 10]{0};
    for (int i = 0; i < len;i++){
        c[i] += a1[i] + b1[i];
        c[i + 1] = c[i] / 10;
        c[i] %= 10;
    }
    if(c[len])
        len++;
    for (int i = len-1; i >=0; i--)
    {
        cout << c[i];
    }
    return 0;
}

放上另外一题：洛谷P1009阶乘之和

代码实现：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[1001]{0}, b[1001]{0};
    int n;
    cin >> n;
    b[0] = 1;
    a[0] = 1;
    for (int i = 2; i <= n;i++){
        for (int j = 0; j < 1000;j++){
            b[j] *= i;
        }
        for (int j = 0; j < 1000;j++){
            b[j + 1] += b[j] / 10;
            b[j] %= 10;
        }
        for (int j = 0; j < 1000;j++){
            a[j] += b[j];
            a[j + 1] += a[j] / 10;
            a[j] %= 10;
        }
    }
    int count{1000};
    while(a[count]==0&&count>0)
        count--;
    for (int i = count; i >= 0;i--){
        cout << a[i];
    }
}

高精减法

处理时被减数一定要比减数大，所以操作过程中要随时检测减数位数，如果减出来的负数，被减数需要向下一位借1。

模板：

#include<bits/stdc++.h>
using namespace std;
int main(){
    bool flag = false;
    string a,b;
    cin >> a >> b;
    if(a==b){//特判
        cout << 0;
        return 0 ;
    }
    int n1=a.length(),n2=b.length();
    if(n2>n1||(n1==n2&&b>a)){//保证大的是被减数
        string temp=a;
        a = b;
        b = temp;
        flag = true;
    }
    n1=a.length(),n2=b.length();
    int c[n1 + 1]{0}, d[n2 + 1]{0};
    for (int i = 0; i < n1;i++){
        c[n1-i-1]=a[i]-'0';//注意字符串从小到大位数逐渐减小，因此应该反存
    }
    for (int i = 0; i < n2;i++){
        d[n2-i-1]=b[i]-'0';
    }
    int ans[n1 + 1]{0};
    int t=0;
    for(int i=0; i < n1;i++){
        c[i]-=t;
        if(i>=n2){
            for (int j = i; j < n1;j++){
                ans[j] = (c[j] + 10)%10;
                if(c[j]<0)
                    c[j + 1]--;
            }
            break;
        }
        ans[i] = (c[i] + 10 - d[i]) % 10;
        if(c[i]-d[i]<0)
            t = 1;//借1
        else
            t = 0;
    }
    int count{n1-1};
    while(ans[count]==0)//去除前置0
        count--;
    if(flag)
        cout << '-';//输出负号
    for (int i = count; i >= 0;i--){
        cout<<ans[i];
    }
    return 0;
}

坑点：

1. 字符串的第一位实际上该数字最高的位数，因此存到数组时要反着存
2. 要用取余操作保证存进答案数组的为正数（用来凑数的坑）
3. 最后要去除前置0，再输出答案

高精乘法

代码模板（高精乘低精）：

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}
//懒得自己写，该模板来自https://www.cnblogs.com/limitedInfinite/p/14747835.html

高精除法

代码模板（高精除低精）：

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )//除法从大的位数开始
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

有关爆精

最后讲讲爆精度这档子事，很多时候我们看到数据范围是$2^{31}$,就觉得不会爆int，很自然的用了int，最后却莫名其妙的过不了。
事实上，两个int类型的数相加或者相乘是很容易爆精度的，很多题就在这设置了一个坑，所以longlong永远的神（雾）。