高精度

高精度的几种情况两个大整数相乘A * B或者相除A / B考的用到的不是很多,就不讲了 .

image-20241103142917554

①大整数存储

大整数在C++里面或者在C里面是如何存下来的.其实是把大整数的每一位存到数组里面去.存的话有一个问题,是高位在前还是低位在前(存在数组里面)

考虑到两个整数相加可能会有进位,这个时候我们把进位放到数组的末尾就是最方便的;如果想在数组的开头补上一个数,就要把整个数组往后移动一位,这是非常麻烦的.

那么我们就决定数组下标是零的元素存储大整数的个位,数组下标是一的元素存储大整数的十位,以此类推.

一句话总结:==就是数组从零开始往后依次存储大整数的从低到高位==

②大整数计算

就是模拟小学的加法,Ai + Bi + 进位 mod 10

pS:a <= 10 和a的位数<= 10 的区别

image-20241108165305653

791高精度加法

==自己的写法==

自己通过在草稿纸上模拟一下,然后提交了一次看看可能的错误,最终ac了

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
#include <iostream>
#include <vector> //vector自带size()函数表示数组的长度,我们就不需要开一个额外的变量去存储 了
using namespace std;
const int N = 1e5 + 10;
vector<int> add(vector<int> &A, vector<int> &B)
{ // 加引用是为了提高效率.如果不加引用 的话,他会把这两个数组copy一遍,花时间
    // 加引用就不拷贝,效率高
    vector<int> C;
    // 我先自己尝试设计一下,看来自己是写出来了
    int t[N];
    t[0] = 0;
    while (A.size() < B.size())
        A.push_back(0);
    while (B.size() < A.size())
        B.push_back(0);
    int i;
    for (i = 0; i < A.size(); i++) // 这里要修改,因为A和B的位数可能不一样
    {
        C.push_back((A[i] + B[i] + t[i]) % 10);
        t[i + 1] = (A[i] + B[i] + t[i]) / 10;
    }
    if (t[i])
        C.push_back(t[i]); // 要处理可能的最高位进位
    return C;
}
int main(void)
{
    string a, b; // 用字符串读进来,存到vector里面去
    vector<int> A, B;
    cin >> a >> b; // 读完之后 a = "123456"这样的形式
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    } // A = [6, 5, 4, 3, 2, 1]'
    for (int j = b.size() - 1; j >= 0; j--)
    {
        B.push_back(b[j] - '0');
    }
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--)
    {
        printf("%d", C[i]);
    }

    return 0;
}

image-20241108173347095

自己写的时候的草稿,可能就自己看得懂,不过放上来总归是好的

0db39731cb4e192ff03b4c187dd2b31

上面放反了,接下来旋转一下

MyDraft

==y总的写法==

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
#include <iostream>
#include <vector> //vector自带size()函数表示数组的长度,我们就不需要开一个额外的变量去存储 了
using namespace std;
const int N = 1e5 + 10;
vector<int> add(vector<int> &A, vector<int> &B)
{ // 加引用是为了提高效率.如果不加引用 的话,他会把这两个数组copy一遍,花时间
    // 加引用就不拷贝,效率高
    vector<int> C;
    // 我先自己尝试设计一下,看来自己是写出来了
    // int t[N];
    // t[0] = 0;
    // while (A.size() < B.size())
    //     A.push_back(0);
    // while (B.size() < A.size())
    //     B.push_back(0);
    // int i;
    // for (i = 0; i < A.size(); i++) // 这里要修改,因为A和B的位数可能不一样
    // {
    //     C.push_back((A[i] + B[i] + t[i]) % 10);
    //     t[i + 1] = (A[i] + B[i] + t[i]) / 10;
    // }
    // if (t[i])
    //     C.push_back(t[i]); // 要处理可能的最高位进位
    // return C;

    // 学习y总的模板写法
    int t = 0;                                         // 我一开始也想这样写把t通过迭代来更新,但是觉得还是用数组美观一些,
    for (int i = 0; i < A.size() || i < B.size(); i++) // 这里i < A.size() || B.size()就是取A和B的最大值
    {
        if (i < A.size()) // 因为i取到A和B长度的最大值,
            // 所以这里的判断可以表明当i >= A.size()&& i < B.size()的时候,
            // 通过一个判断,让t实现加0的效果(不执行t += A[i]就是让t加0)
            // 跟我的需要A.push_back(0);的写法来说,这个效率更高
            t += A[i];
        if (i < B.size())
            t += B[i];
        C.push_back(t % 10);
        t = t / 10;
    }
    if (t)
        C.push_back(1);
    return C;
}
int main(void)
{
    string a, b; // 用字符串读进来,存到vector里面去
    vector<int> A, B;
    cin >> a >> b; // 读完之后 a = "123456"这样的形式
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    } // A = [6, 5, 4, 3, 2, 1]'
    for (int j = b.size() - 1; j >= 0; j--)
    {
        B.push_back(b[j] - '0');
    }
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--)
    {
        printf("%d", C[i]);
    }

    return 0;
}

个人错误

把i < A.size() || i < B.size()写成i < A.size() || B.size()是大错特错.

后者就算是A.size() || B.size()先结合我也不知道要怎么理解,最后结果可能是两个整数==按位或==的结果,而不是你能保证的逻辑就是i < A.size()和i < B.size()表示的两个true或者false的表达式来==逻辑或==.

就和你把i < 7 || i < 10写成 i < (7 || 10),即i < 15的形式明显是==错误的==.

{(7 || 10) 就是 0111 || 1010 = 1111等于15结果就是i < 15明显和i < 7 || i < 10的结果不一样}

要牢记

注意的点

后面很多笔记都写错了,要改成i < A.size() || i < B.size()的形式,但是没时间了,所以知道我想说的意思就行了 .

注意,这里i < A.size() || B.size()就是取A和B的最==大==值,是最大值不是最小值.两者至少一个为true就能做到整个为true

如果是 i < A.size() && B.size()就是取A和B的最==小==值,两者至少一个为false就能做到整个为false

1
for (int i = 0; i < A.size() || B.size(); i++) // 这里i < A.size() || B.size()就是取A和B的最大值
y总对代码的讲解

用数组表示整数的时候,

数组的第零位表示的是大整数的个位,

数组的第一位表示的是大整数的十位,

以此类推

t 表示上一位的进位,最开始的时候进位是0,所以一开始t = 0

每一次看Ai和Bi,如果有的话,就加上Ai(没有的话就不加,相当于加上零);如果有的话,就加上Bi(没有的话就不加,相当于加上零)

当前这一位Ci = 三者相加 mod10,给前一位的进位就是三者相加 / 10

最后循环结束的时候,i == A.size()和B.size()的最大值,此时可能向更高位进一(当然如果进零,就不用C.push_back(t);不然最后结果可能是 1 + 1 = 02明显不合题意)

因此最后要加上

1
2
if (t)
    C.push_back(1);

这个和给的模板不太一样,但我还是打算记住这个模板,感觉更加的对称和合理

792高精度减法

我要怎么知道A大还是B大了,能不能计算出负数的结果了

我们高精度减法的模板是要保证A >= B的,如果A < B 的话,我们就换着成 B - A最后在结果面前加上负号

个人的写法

自己一开始想把cmp A 和B的过程写到sub(A, B)里面,但是发现这样子太复杂了,而且自己要定义全局变量flag来判断有没有交换过A和B.事实上写到最后我怀疑是swap(A, B)这个函数根本就没有交换两者.然后就写不下去了.

抛开swap函数不谈,我这种思路这个把cmp A 和B的过程写到sub(A, B)里面的这种思路就是错的,我记得有个外国人人说的一句话:编写一个函数的时候,给这个函数的功能越简单越小就越好.

keep it simple,keep it good(可能是这样说的)

中文网络上也能找类似的话

函数越短小，功能越集中,就越能取于一个好名称.

因此我定义的sub(A, B)就应该仅仅是一个当A >= B的时候,完成减法的函数

至于A < B 的话,我们就换着成 B - A最后在结果面前加上负号这种操作,我们再多写几个函数,然后再main()主函数里面通过一些逻辑的代码将这几个函数组合起来就行了.

因此我们专门写一个cmp函数

在这种多个功能明确的函数的思路之下,我写的代码ac了

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <vector> //vector自带size()函数表示数组的长度,我们就不需要开一个额外的变量去存储 了
using namespace std;
const int N = 1e5 + 10;
// A < B,返回false
// A >= B,返回true

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size())
        return false;
    else if (A.size() > B.size())
        return true;
    else
    {
        for (int i = A.size() - 1; i >= 0; i--)
        {
            if (A[i] > B[i])
            {
                return true;
                // break;
            }
            else if (A[i] < B[i])
                return false;
            else
                ;
        }
    }
    return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{ // 加引用是为了提高效率.如果不加引用 的话,他会把这两个数组copy一遍,花时间
    // 加引用就不拷贝,效率高
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++)
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t -= B[i];
        if (t < 0)
        {
            t += 10;
            C.push_back(t);
            t = -1;
        }
        else
        {
            C.push_back(t);
            t = 0;
        }
    }

    return C;
}
int main(void)
{
    string a, b; // 用字符串读进来,存到vector里面去
    vector<int> A, B;
    cin >> a >> b; // 读完之后 a = "123456"这样的形式
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    } // A = [6, 5, 4, 3, 2, 1]'
    for (int j = b.size() - 1; j >= 0; j--)
    {
        B.push_back(b[j] - '0');
    }
    // 这里直接用compare来比较两个vector<int>类型就行了,不用自己写函数比较
    if (cmp(A, B))
    {
        auto C = sub(A, B);
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i > 0; i--)//最后一个数,不管是不是0都要输出了.
        {
            if (C[i] != 0)
                break;
        }
        for (; i >= 0; i--)
        {

            printf("%d", C[i]);
        }
    }
    else
    {
        auto C = sub(B, A);
        cout << "-";
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i > 0; i--)
        {
            if (C[i] != 0)
                break;
        }
        for (; i >= 0; i--)
        {

            printf("%d", C[i]);
        }
    }
    return 0;
}

对这段代码的理解

1
2
3
4
5
6
7
8
9
10
11
12
// 前面连续的0要略过去
       int i = C.size() - 1;
       for (; i > 0; i--)//最后一个数,不管是不是0都要输出了.
       {
           if (C[i] != 0)
               break;
       }
       for (; i >= 0; i--)
       {

           printf("%d", C[i]);
       }

这个和&&的感觉很像,就是第一个for循环结束是收到两个条件的影响.一是i == 0;二是C[i] == 0从而break导致的循环结束.

那我就用表格尝试着理解一波

image-20241108214147489

把i > 0当做expr1; C[i] == 0当做expr2

如果某次循环中情况是 true && false ,则循环结束.此时的情况是i > 0且找到了第一个不等于0的数.退出原因是因为找到了第一个不等于0的数

如果某次循环中情况是 true && true ,则循环进行下一轮循环.此时的情况是i > 0且当下的数等于0,所以还要在下一轮循环里面找,循环不退出.

如果某次循环中情况是 false && true ,或者是false && false.则循环结束.此时的情况是i == 0,epxr2表达式的情况根本就不用关心,不用去管.(我不用去管,C++编译器也不会去管.)此时循环退出的原因就是i == 0,而如果你问我为什么i–一直到了0,就是在i–的过程中,每一个数都== 0.

感觉这里和双指针模板里面对while (j < i && check(i, j))j++;这一段的理解是一样的.

1
2
3
4
5
6
for (i = 0, j = 0; i < n; i ++){
	while (j < i && check(i, j))
        j++;
    
    // do something
}

在上面理解的基础上,对这个题干而言,

我们原意要过滤到一个整数前面的所有连续的0,直到遇到第一个非0的数停止,保证此时z指针i指向这第一个非0的数,或者一直没遇到非0的数,此时i就== -1.

特殊情况如果所有的数都是零,那么就要输出一个0.本来是可以在代码里面加一个判断,如果i == -1,我们就输出0 的.

但是我为了简便,所以修改了范围,把for (; i >= 0; i--)改成了for (; i > 0; i--),也就是说当指针i不断的i–,当i指向最后一位如果非0,我们输出最后一位,最后一位如果是0,我们也输出最后一位,此时最后一位刚好就是0;

反正我这么结果是ac了.可能不太好理解,我改成 本来是可以在代码里面加一个判断,如果i == -1,我们就输出0 的 这个逻辑试试

修改后的代码也ac了,说明我的逻辑没有问题

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector> //vector自带size()函数表示数组的长度,我们就不需要开一个额外的变量去存储 了
using namespace std;
const int N = 1e5 + 10;
// A < B,返回false
// A >= B,返回true

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size())
        return false;
    else if (A.size() > B.size())
        return true;
    else
    {
        for (int i = A.size() - 1; i >= 0; i--)
        {
            if (A[i] > B[i])
            {
                return true;
                // break;
            }
            else if (A[i] < B[i])
                return false;
            else
                ;
        }
    }
    return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{ // 加引用是为了提高效率.如果不加引用 的话,他会把这两个数组copy一遍,花时间
    // 加引用就不拷贝,效率高
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++)
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t -= B[i];
        if (t < 0)
        {
            t += 10;
            C.push_back(t);
            t = -1;
        }
        else
        {
            C.push_back(t);
            t = 0;
        }
    }

    return C;
}
int main(void)
{
    string a, b; // 用字符串读进来,存到vector里面去
    vector<int> A, B;
    cin >> a >> b; // 读完之后 a = "123456"这样的形式
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    } // A = [6, 5, 4, 3, 2, 1]'
    for (int j = b.size() - 1; j >= 0; j--)
    {
        B.push_back(b[j] - '0');
    }
    // 这里直接用compare来比较两个vector<int>类型就行了,不用自己写函数比较
    if (cmp(A, B))
    {
        auto C = sub(A, B);
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i >= 0; i--)
        {
            if (C[i] != 0)
                break;
        } // 去掉前面所有连续的零
        if (i >= 0) // 遇到了第一个非零数
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else // 没遇到非零数,也就是所有数都是零
            cout << 0;
    }
    else
    {
        auto C = sub(B, A);
        cout << "-";
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i >= 0; i--)
        {
            if (C[i] != 0)
                break;
        } // 去掉前面所有连续的零
        if (i >= 0) // 遇到了第一个非零数
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else // 没遇到非零数,也就是所有数都是零
            cout << 0;
    }
    return 0;
}

具体的修改的部分看这里

将

1
2
3
4
5
6
7
8
9
10
11
12
// 前面连续的0要略过去
       int i = C.size() - 1;
       for (; i > 0; i--)//最后一个数,不管是不是0都要输出了.
       {
           if (C[i] != 0)
               break;
       }
       for (; i >= 0; i--)
       {

           printf("%d", C[i]);
       }

修改成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i >= 0; i--)
        {
            if (C[i] != 0)
                break;
        } // 去掉前面所有连续的零
        if (i >= 0) // 遇到了第一个非零数
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else // 没遇到非零数,也就是所有数都是零
            cout << 0;

个人还是决定以后都写第二种,第一种绕的弯多,自己也不熟练,第二种的逻辑自己算是很熟练了.

PS:

前面我想出第一种写法的大佬想法是很粗糙的,事实上我连第二种没想出来就直接凭借直觉写了第一种,这是很不好的.我现在既然两种写法都ac了.我就好好的分析一波

首先第二种写法是很好理解的,不好理解的话可以见我的这一片博客第二章 数据结构（一）的单调栈章节

image-20241108221358541

在第二种写法的基础上看第一种写法:

第二种写法循环结束两种情况,根据题意我们可以拆解出两种情况.

第一个情况是expr1为true,退出条件就是expr2为false,也就是在i的合法范围内遇到了第一个非零数,我们从i指向的第一个非零数开始直接往后依次输出就够了.

第二个情况是i的值= -1,那么就是expr1为false,expr2是什么都不用管.退出条件就是一直没遇到非0 的数,所以一直i–直到i = -1;那么我们的处理就是输出一个0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i >= 0; i--)
        {
            if (C[i] != 0)
                break;
        } // 去掉前面所有连续的零
        if (i >= 0) // 遇到了第一个非零数
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else // 没遇到非零数,也就是所有数都是零
            cout << 0;

根据上面的两种情况,我们可以拆解出三种情况:

第一种情况:

如果我们在//去掉前面所有连续的零这个for循环里面不判断C[0]这个数,那么在i>0的条件下是因为expr1为true而expr2为false的话,就是因为遇到了第一个非零数退出的循环,那么从指针i指向的第一个非零数开始依次往后输出的结果==肯定是和第二种写法是一样的==.因为同样的C[]数组,如果能够在在i>0的条件下是因为expr1为true而expr2为false的话,就是因为遇到了第一个非零数退出的循环,那么从指针i指向的位置是一样 的,且依次往后输出的代码是一样的,都是下面这段代码,从i指向的元素一直输出到C[0]

1
2
3
4
5
for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }

第二种情况:

如果expr1为false而expr2不用管的话,此时i == 0,至少在i > 0 的情况下,所有的C[i]都是零.最后一个数也就是C[0]这个数,如果他是非零数,我们就从输出C[0],这刚好就是从C[i] (i是第一个非零元素的指针)依次往后输出的子集,==所以肯定是对的==;

第三种情况:

如果expr1为false而expr2不用管的话,此时i == 0,至少在i > 0 的情况下,所有的C[i]都是零.最后一个数也就是C[0]这个数.如果C[0]是零,第二种写法我们就让i–,然后i非法,我们退出循环,然后进入else判断,我们就cout << 0;,但是作为第一种写法,我们看到了输出零就等于输出刚好等于零 的C[i],所以我们直接输出C[i],==因此也肯定是对的==

第一种情况加第二种情况就是第二种写法的第一种情况

第三种情况就是第二种写法的第二种情况

也就是把第二种写法的两种情况,变成了第一种写法的三种情况来考虑(虽然思考量变多了,但是代码却可以合并成一段,从代码上变短了,但是思考量却变多了,很不推荐.)

为了验证确实是分成这三种情况,并且这三种情况是对的,我写下面这样的代码也ac了.三种情况,每一种都是使用相同的代码段,说明就是三种情况对应的代码块一样.从代码上变短了,但是思考量却变多了,很不推荐 

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <vector> //vector自带size()函数表示数组的长度,我们就不需要开一个额外的变量去存储 了
using namespace std;
const int N = 1e5 + 10;
// A < B,返回false
// A >= B,返回true

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size())
        return false;
    else if (A.size() > B.size())
        return true;
    else
    {
        for (int i = A.size() - 1; i >= 0; i--)
        {
            if (A[i] > B[i])
            {
                return true;
                // break;
            }
            else if (A[i] < B[i])
                return false;
            else
                ;
        }
    }
    return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{ // 加引用是为了提高效率.如果不加引用 的话,他会把这两个数组copy一遍,花时间
    // 加引用就不拷贝,效率高
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++)
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t -= B[i];
        if (t < 0)
        {
            t += 10;
            C.push_back(t);
            t = -1;
        }
        else
        {
            C.push_back(t);
            t = 0;
        }
    }

    return C;
}
int main(void)
{
    string a, b; // 用字符串读进来,存到vector里面去
    vector<int> A, B;
    cin >> a >> b; // 读完之后 a = "123456"这样的形式
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    } // A = [6, 5, 4, 3, 2, 1]'
    for (int j = b.size() - 1; j >= 0; j--)
    {
        B.push_back(b[j] - '0');
    }
    // 这里直接用compare来比较两个vector<int>类型就行了,不用自己写函数比较
    if (cmp(A, B))
    {
        auto C = sub(A, B);
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i > 0; i--) // 最后一个数,不管是不是0都要输出了.
        {
            if (C[i] != 0)
                break;
        }
        if (i > 0)
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else
        {
            if (i == 0 && C[0] != 0)
                for (; i >= 0; i--)
                {

                    printf("%d", C[i]);
                }
            else if (i == 0 && C[0] == 0)
                for (; i >= 0; i--)
                {

                    printf("%d", C[i]);
                }
        }
    }
    else
    {
        auto C = sub(B, A);
        cout << "-";
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i > 0; i--) // 最后一个数,不管是不是0都要输出了.
        {
            if (C[i] != 0)
                break;
        }
        if (i > 0)
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else
        {
            if (i == 0 && C[0] != 0)
                for (; i >= 0; i--)
                {

                    printf("%d", C[i]);
                }
            else if (i == 0 && C[0] == 0)
                for (; i >= 0; i--)
                {

                    printf("%d", C[i]);
                }
        }
    }
    return 0;
}

image-20241109005719602

换一种清晰的也是对的,结果也ac了

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <vector> //vector自带size()函数表示数组的长度,我们就不需要开一个额外的变量去存储 了
using namespace std;
const int N = 1e5 + 10;
// A < B,返回false
// A >= B,返回true

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size())
        return false;
    else if (A.size() > B.size())
        return true;
    else
    {
        for (int i = A.size() - 1; i >= 0; i--)
        {
            if (A[i] > B[i])
            {
                return true;
                // break;
            }
            else if (A[i] < B[i])
                return false;
            else
                ;
        }
    }
    return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{ // 加引用是为了提高效率.如果不加引用 的话,他会把这两个数组copy一遍,花时间
    // 加引用就不拷贝,效率高
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++)
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t -= B[i];
        if (t < 0)
        {
            t += 10;
            C.push_back(t);
            t = -1;
        }
        else
        {
            C.push_back(t);
            t = 0;
        }
    }

    return C;
}
int main(void)
{
    string a, b; // 用字符串读进来,存到vector里面去
    vector<int> A, B;
    cin >> a >> b; // 读完之后 a = "123456"这样的形式
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    } // A = [6, 5, 4, 3, 2, 1]'
    for (int j = b.size() - 1; j >= 0; j--)
    {
        B.push_back(b[j] - '0');
    }
    // 这里直接用compare来比较两个vector<int>类型就行了,不用自己写函数比较
    if (cmp(A, B))
    {
        auto C = sub(A, B);
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i > 0; i--) // 最后一个数,不管是不是0都要输出了.
        {
            if (C[i] != 0)
                break;
        }
        if (i > 0)
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else
        {
            if (i == 0 && C[0] != 0)
                cout << C[0];
            else if (i == 0 && C[0] == 0)
                cout << 0;
        }
    }
    else
    {
        auto C = sub(B, A);
        cout << "-";
        // 前面连续的0要略过去
        int i = C.size() - 1;
        for (; i > 0; i--) // 最后一个数,不管是不是0都要输出了.
        {
            if (C[i] != 0)
                break;
        }
        if (i > 0)
            for (; i >= 0; i--)
            {

                printf("%d", C[i]);
            }
        else
        {
            if (i == 0 && C[0] != 0)
                cout << C[0];
            else if (i == 0 && C[0] == 0)
                cout << 0;
        }
    }
    return 0;
}

image-20241109010026683

结语:

这里只是做一个补充,如果是我的话,一辈子都不想再回忆一遍自己当时是怎么直觉写出第一种写法的,反正我以后都写逻辑清晰好理解的第二种写法.第一种需要偶然也就是C[0]刚好等于0,我讨厌第一种!!!!!==你应该把你的较真用到刀刃上,而不是这里.较真不是坏的,但是发力的点不好的话,只会变成伤害自己的钻牛角尖.其实究竟怎么想不重要了,反正我以后只会用第二种方式,拿到分数就好,更多的时间拿更多的分数,而不是在这里搞所谓的”喜欢研究”,完全是浪费时间==

y总对代码的讲解

cmp函数怎么写,

看来自己昨天那么较真还是有效果的,至少y总也讲到了最后一位不做处理,不管是不是零都要直接输出了.

下面这段是我自己写的,ac了

1
2
3
4
5
6
for (int i = A.size() - 1; i > 0; i--)
    if (C[i] == 0)
        C.pop_back();
    else
        break;

整体代码

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
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
using namespace std;
// 改题目假定 A 和B都是正整数
// 如果不是正整数,那就一定可以转换成 A的绝对值和B的绝对值想加减的问题,最后要不要加一个负号,在main里面分类讨论就行了.
const int N = 100010;
vector<int> sub(vector<int> &A, vector<int> &B);
bool cmp(vector<int> &A, vector<int> &B);
int main(void)
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; i--)
    {
        B.push_back(b[i] - '0');
    }
    if (cmp(A, B))
    {
        vector<int> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--)
        {
            printf("%d", C[i]);
        }
    }
    else
    {
        vector<int> C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--)
        {
            printf("%d", C[i]);
        }
    }

    return 0;
}
// A >= B return true
// A < B return false
bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size())
        // 是大于号不是减法,如果结果是负数那整数转换成bool类型,等于true;
        // 但此时A < B结果应该是 false
        return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--)
    {
        if (A[i] != B[i])
            return A[i] > B[i];
    }
    return true; // 最后 A == B ,我们返回true
}
vector<int> sub(vector<int> &A, vector<int> &B)
// 默认A >= B
//,如果A< B则交换的行为直接在外面调用函数传入实参的时候交换A和B 的位置,
// 包括最后要先输出"-"的话,也是在main函数里面放在printf C容器之前,
// 反正你一个函数的功能是越简单越明确越好
{
    vector<int> C;
    int t = 0;
    // 此时A的size一定是大于等于B的 size
    for (int i = 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;
    }
    // 从A.size() - 1位开始(包括A.size() - 1位),最前面的数往后可能是一连串的零
    // 因此要做处理,对整数高位做处理就是对vector<int> 的末尾做处理
    for (int i = A.size() - 1; i > 0; i--)
        if (C[i] == 0)
            C.pop_back();
        else
            break;

    // 因为A >= B所以不会像加法那样出现要想最高位的上面一位进位
    // 在减法这里就是不可能向最高位的上面一位借位,不然就A< B了,矛盾
    //  所以结束循环后的t 一定是0,不用将t pushback到A.size() 位,,因此我们直接返回C
    return C;
}

==下面这段是y总的==

一定要判断一下B[i]是否存在,因为B[i]的位数可能比A[i]的位数要少,存在的话我们再减去B[i];不减B[i]就是等于减去给高位补上的0.

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
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
using namespace std;
// 改题目假定 A 和B都是正整数
// 如果不是正整数,那就一定可以转换成 A的绝对值和B的绝对值想加减的问题,最后要不要加一个负号,在main里面分类讨论就行了.
const int N = 100010;
vector<int> sub(vector<int> &A, vector<int> &B);
bool cmp(vector<int> &A, vector<int> &B);
int main(void)
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; i--)
    {
        B.push_back(b[i] - '0');
    }
    if (cmp(A, B))
    {
        vector<int> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--)
        {
            printf("%d", C[i]);
        }
    }
    else
    {
        vector<int> C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--)
        {
            printf("%d", C[i]);
        }
    }

    return 0;
}
// A >= B return true
// A < B return false
bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size())
        // 是大于号不是减法,如果结果是负数那整数转换成bool类型,等于true;
        // 但此时A < B结果应该是 false
        return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--)
    {
        if (A[i] != B[i])
            return A[i] > B[i];
    }
    return true; // 最后 A == B ,我们返回true
}
vector<int> sub(vector<int> &A, vector<int> &B)
// 默认A >= B
//,如果A< B则交换的行为直接在外面调用函数传入实参的时候交换A和B 的位置,
// 包括最后要先输出"-"的话,也是在main函数里面放在printf C容器之前,
// 反正你一个函数的功能是越简单越明确越好
{
    vector<int> C;
    int t = 0;
    // 此时A的size一定是大于等于B的 size
    for (int i = 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;
    }
    // 从A.size() - 1位开始(包括A.size() - 1位),最前面的数往后可能是一连串的零
    // 因此要做处理,对整数高位做处理就是对vector<int> 的末尾做处理
    // 去掉前导零
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    // y总的写法确实好理解一些,以后就用y总的写法

    // 因为A >= B所以不会像加法那样出现要想最高位的上面一位进位
    // 在减法这里就是不可能向最高位的上面一位借位,不然就A< B了,矛盾
    //  所以结束循环后的t 一定是0,不用将t pushback到A.size() 位,,因此我们直接返回C
    return C;
}

793高精度乘法

b是较小得数,把b看成一个整体去和A去乘法.而不是去一位一位乘法(和我们一般的乘法一样)

前面高精度加法或者减法的进位不是零就是一,这在数学上是肯定的

但是我这里的高精度乘法的b还看做一个整体,进位很复杂.个人认为 for (int i = 0; i < A.size() || t; i++)这里的循环在i >= A.size() 的时候t > 0的时候循环了可能不止一轮,所以

1
2
C.push_back(t % 10);
t /= 10;

刚好能逐位的push到C的末尾.很精妙的代码,记住就好.

(y总原话,t是不会剩下的只要t不是零,我们就一直循环,所以我们其实是把两个循环结合到一起去了.

)

猜对了,刚刚y总讲了t 可能等于101,所以就说这里t向前的进位就是 t / 10 =10而不是1或者零. (y总原话,那就只剩下10进到下一位)

image-20241109112026229

y总的写法

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
#include <iostream>
#include <vector>
using namespace std;

const int N = 100010;
vector<int> mul(vector<int> &A, int b);
int main(void)
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');

    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
    return 0;
}
vector<int> mul(vector<int> &A, int b)
{
    // 先尝试自己写
    vector<int> C;
    int t = 0;
    // 这里i < A.size() || t你用我之前的true和false分别分四种情况看一看就能理解了
    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;
}

794高精度除法

这个算法是一个高精度的数除以一个低精度的数,就是A除以 b

除法正着来存好一些,但是很多时候都是加减乘除混合的,所以为了统一,我们都是倒着来存储.

除法从最高位开始除,前面加减乘都是从最低位开始

所以最后放到C里面的要reverse,最后千万记得去掉前导零

1000 / 9 的商就是0111余数是1

y总的写法

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
vector<int> div(vector<int> &A, int b, int &r); // 余数用引用类型返回,在函数内修改余数会影响main函数内的余数大小
int main(void)
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    int r;
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
    cout << endl;
    cout << r << endl;
    return 0;
}
// 计算 A / b,商是C,余数是r
vector<int> div(vector<int> &A, int b, int &r) // 余数用引用类型返回,在函数内修改余数会影响main函数内的余数大小
{
    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;
    }
    // 逆转C
    reverse(C.begin(), C.end());
    // 去除前导零
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

讲解

被y总带偏了,把

1
2
C.push_back(r / b); // 可能会有前导零
r %= b;

写成

1
2
C.push_back(r / 10); // 可能会有前导零
r %= 10;

千万不能记错了.

商是余数整除b,余数是余数mod b

前缀和和差分

795. 前缀和

image-20241109163412812

前缀和一定是从1开始

①Si如何求:Si可以递推一遍,定义的时候S[0] = 0,原因是我们让原数组a的下标从一开始那么我们的S[0]就可以不对应任何变量,就可以让S[0]等于0.

好处是可以处理边界.[1, 10]的和直接求S[10] - S[1 - 1]等于S[10] - S[0]明显等于S[10],为了统一我们就定义S[0] 等于0

1
2
3
for (int i = 1; i <= n; i ++){
    S[i] = S[i - 1]  + a[i];
}

②Si用来干嘛的,S[i] 的作用

能快速求出来原数组里面一段数的和.例如让你求原数组里面[l, r]的数的和

没有前缀和数组的话,时间复杂度是O(n);有前缀和数组的话直接S[r] - S[l - 1],一次运算就能算出来任意一段区间内的和,时间复杂度是 O(1);

前缀和数组的预处理是O(n)的,每次询问是O(1)的

y总的写法

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
#include <iostream>

using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main(void)
{

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    // 前缀和的初始化
    s[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    while (m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

796. 子矩阵的和

上面的是一维前缀和,,下面讲二维前缀和

快速求出来一段子矩阵里面的和

S[i,j]表示的是左上角所有元素的和

蓝色小正方形的面积等于S,S的计算公式见我的草稿纸.明显我的草稿纸里面的内容写错了

二维前缀和

用表格看会更加的清楚

image-20241109174022475

image-20241109174037138

减完一之后就没有边界问题了.没错,我从没看出有边界问题过.

如何推导S[i, j] 

1
2
3
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++)
        S[i][j] = a[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1] [j - 1];//可以再图形上面来理解.

这里保持和一位前缀和一样,都是从1开始的.也就是a11开始

y总的写法

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
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main(void)
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    // 初始化前缀和数组
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) // 这里吧m写成n了
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];//算前缀和
    while (q--)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);//算子矩阵的和
    }
    return 0;
}

个人错误

对二维数组的i对应n,j对应m还是不够熟练,敲错了很难排查,千万不能再错 了.

1
for (int j = 1; j <= m; j++) // 这里吧m写成n了

初始化前缀和二维数组的时候,好理解这个

但是这里也出错了, 就是连续两次将- s[i - 1][j - 1]写成- s[i][j].很明显递推应该是s[i - 1][j - 1]递推到s[i][j] 的,前面不能饭第三次错误.

1
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

但是计算对应蓝色小正方形的时候,我那个草稿的图示有一个细节没标出来,就是蓝色小正方形是四条边也是由元素组成 的,我们要保留四条边.因此应该写成这样子

对于左上方的点x1, y1,所有的-1都是在x1和y1后面减去的1

1
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);

797. 差分

差分就是前缀和的逆运算

test

image-20241109174404238

构造其实没有那么重要

假设我们已经得到b数组了,那我们可以由O(n)的时间从b数组得到a数组,只求一遍前缀和就可以

image-20241109175027224

image-20241109175256243

image-20241109181526895

见图回忆,将时间复杂度从O(n)降到O(1)

自己的写法ac了

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    // 构造差分数组
    for (int i = 1; i <= n; i++)
    {
        b[i] = a[i] - a[i - 1];
    }
    while (m--)
    {
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);

        // 操作
        b[l] += c;
        b[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = a[i - 1] + b[i];
        cout << a[i] << " ";
    }
    return 0;
}

y总的写法

假定原数组一开始的 时候全部都是零,那么差分数组也全部都是零.

但是已经给出来了a1到an,我们可以看成做了n次插入操作

第一次是把原数组的[1, 1]这个区间加上a1

第二次是把原数组的[2, 2]这个区间加上a2

….

第n次是把原数组的[n, n]这个区间加上an

所以发现差分不用你构造,你这样子做直接就出来了.

总结差分就一个操作

如果想让原数组的[l, r]整段加一个c的话

那就让b[l] + c 和 b[r + 1] - c好了

二维差分也是一样 的道理

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N]; // 全局变量默认为零,好像是:????
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}
int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
        insert(i, i, a[i]); // 其实也就是让b[i] = a[i] - a[i - 1];
    while (m--)
    {
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);
        insert(l, r, c);
    }
    // 对差分数组求一遍前缀和就是原来的数组a
    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", b[i]);

    return 0;
}

798. 差分矩阵

二维差分也是一样的道理,就是二维前缀和的逆过来.

这里也不用考虑如果构造,因为我们可以先假定初始的时候aij = 0

那么bij显然也等于0(一种差分方式)

接着遍历原来矩阵a中的每一个值,把它插一遍就行了,这样bij就被构造出来了.

(这样就不用我们考虑如何构造了,只需要考虑如何去更新就可以了.

==因为我们发现构造其实是可以用修改操作来做的.==我们可以先假定初始的时候aij = 0

那么bij显然也等于0(一种差分方式)

接着遍历原来矩阵a中的每一个值,把它插一遍就行了,这样bij就被构造出来了

)

image-20241109184551405

image-20241109184609364

自己写的ac了

有意思的是如果我const int N = 1010;写成const int N = 100010;

我的vscode和acwing的ide都会报错问题是

image-20241109190553527

原因是

image-20241109190619216

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
#include <iostream>
using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main(void)
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);

    while (q--)
    {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            b[i][j] = b[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            printf("%d ", b[i][j]);
        printf("\n");
    }
    return 0;
}

y总的写法和我一样,我这次算是碰上y总的写法了

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
#include <iostream>
using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main(void)
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);

    while (q--)
    {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            b[i][j] = b[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            printf("%d ", b[i][j]);
        printf("\n");
    }
    return 0;
}

所以可以发现差分的核心就是这个insert函数

1
2
3
4
5
6
7
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

DONE

==最终的记忆还是要看文字描述的思路,然后自己慢慢回忆起来代码是怎么写的.要有从精简的文字概括到复现代码的过程才能记得牢靠.==

这一节的笔记就到这里了.学完之后立马自己重新写一遍还是很有效果的.以后要一直坚持,然后复习的时间规律我之后再说.