1.高精度运算

1.高精度加法

「题解：」

  • 对输入的两个 整数字符串进行倒序添加进数组，以方便从低位到高位的加法运算，这样如果最后有进位，直接在数组末尾进行push_back就行。
  • 然后判断一下那个数大，默认A最大，加法只用考虑长度即可，长度相同加法无所谓。
  • 之后进行按位相加，0~9相加不会超过 20，进位 t 只用考虑 1 or 0。
  • 每次需要加的位需要进行对10取余，即 （ai + bi） % 10，因为加法、只会把个位的数加上去，十位则为进位。
  • 然后判断 t ，看是否 进位即可。

「注意：」

  • 这里 一开始 t为0，t 直接加a[i]，之后看是否在 B的长度内，在就再加上bi，t 再除以10判断是否有进位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
vector<int> A, B, C;

void getArr(vector<int> &a, vector<int> &b)
{
    // a 一定是长度长的那个
    int t = 0; // t为进位
    int i = 0;
    for(; i < a.size();++i)
    {
        t += (a[i]);
        if(i < b.size()) t += b[i];
        C.push_back(t  % 10);
        t /= 10;
    }
    if(t != 0) C.push_back(t);

}
int main()
{

    string s1, s2;
    cin >> s1 >> s2;

    for (int i = s1.length() - 1; i >= 0; --i)
    {
        A.push_back(s1[i] - '0');
    }
    for (int i = s2.length() - 1; i >= 0; --i)
    {
        B.push_back(s2[i]- '0');
    }

    if (A.size() >= B.size())
    {
        getArr(A, B);
    }
    else
    {
        getArr(B, A);
    }

    reverse(C.begin(),C.end());
    for(auto i : C)
    {
        cout << i << "";
    }
    cout << endl;
    return 0;
}

2.高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <bits/stdc++.h>
using namespace std;
vector<int> A, B, C;
bool fuhshu = false;

// 判断 B > A
bool cmp(vector<int> &A, vector<int> &B)
{
    if (B.size() >  A.size())
        return true;

    if (B.size() == A.size())
    {
        for (int i = A.size() - 1; i >= 0; --i)
        {   
            // 987 986
            if(A[i] != B[i]) return B[i] > A[i];
        }
    }
    return false;
}

// C = A - B
void getArr(vector<int> &a, vector<int> &b)
{
    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 and C.back() == 0 )
    {
        C.pop_back();
    }
}
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    for (int i = s1.length() - 1; i >= 0; --i)
    {
        A.push_back(s1[i] - '0');
    }
    for (int i = s2.length() - 1; i >= 0; --i)
    {
        B.push_back(s2[i] - '0');
    }

    // 判断是否是负数
    // 1.如果 a的长度大于b，则一定a大
    // 2.如果位数相同，则判断开头谁大

    if (cmp(A, B))
    {
        getArr(B, A);
        fuhshu = true;
    }
    else
    {
        getArr(A, B);
    }

    if(fuhshu) cout << '-';
    for(int i = C.size() - 1;i >= 0;--i) 
    {

        cout << C[i] <<"";
    }
    cout << endl;
    return 0;
}


3.高精度乘法

4.高精度除法

2.前缀和

1.一维前缀和

2.二维前缀和

3.差分

1.一维差分

2.二维差分