YXC 算法基础笔记（二）

算法笔记完全是按照y总的基础班的录像进行整理，标题与直播录像顺序一致

高精度加减程度，重要的是处理“中间数”，即每段代码中的t，根据加减乘除运算方法不同，对t的处理也打不相同，同时也不要忽略对于前导0的处理。
基本上总结起来就是，加法比较简单只需要判断是否需要进位1，而减法需要考虑是否借位。乘法的“进位”可能大一些，但是和加法类似

1. 大数相加:

C++中大数相加，需要利用STL中的vector，java和python中不需要自己写算法。

这个算法纯粹是利用到vector来存储位数较多的所谓“大数”，只需要注意，是从低到高存储相应位的数字，并且判断两数相加是否需要进位即可。

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int>& A, vector<int>& B)
{
    vector<int> C;

    int t = 0; // 利用t来判断是否需要进位
    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];
        C.push_back(t % 10);
        t /= 10; // 大于10则进位1，否则进位0
    }

    if (t) C.push_back(t); // 判断最高位是否需要进位
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;

    cin >> 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');

    auto C = add(A, B);

    for (int i = C.size() - 1; i >= 0; i--) printf("%d",C[i]);
    return 0;

}

2. 大数相减：

与大数相加类似，唯一差别就在于相加考虑到进位，相减则考虑到借位，并且有明确的减数和被减数。A - B的前提是A要大于等于B（即暂不考虑负数）。所以要增加一步判断，A, B谁是减数，谁是被减数。而对于每一位的运算结果，则要考虑结果是否为负，结果为负则要进行借位操作。

// 判断是否有 A >= B
bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) 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; // 两个数相等，也是成立的
}

vector<int> minus(vector<int>&A, vector<int>& B) // A - B
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i++)
    {
        t = A[i] - t; // 如果前面借位， A[i]的值要减去1
        if (i < B.size()) t -= B[i]; // 是否需要减去b可以单独考虑
        C.push_back((t + 10) % 10); // 借位和不借位数是一样的
        if (t < 0) t = 1; // 判断是否存在借位
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); 

    return C;
}

3. 大数相乘

大数相乘和大数加法类似，但因为是一个很大很大的数乘以一个相对没那么大的数，所以运算的过程也不太一样。是由大数的每一位乘以相对小数，然后判断是否需要进位。

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int>& A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++)
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10; // 这就是大数乘法运用到的方法，本质上还是乘法分配律
    }

    while (t)
    {
        C.push_back(t % 10);
        t /= 10;
    }

    // 还需要去掉前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();    

    return C;

}

int main()
{
    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;
}

4. 高精度除法

首先要理解正常计算除法的步骤与方法，首先求每一位除以除数得出余数，然后余数加入到下一次的运算。

vector<int> dic(vector<int>& A, int b, int& r) // 注意高精度除法，vector最低位存放的是最高位
{
    vector<int> C;
    r = 0; // 需要引用传递一个余数
    for (int i = A.size(); i >= 0; i--) // 从最高位开始进行计算
    {
        r= r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }

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

    return C;

}

5. 前缀和问题

为了方便前缀和一般都是从1开始写起

重要的是前缀和中的思想，第l到第r个数的和，代码很简单

#include <iostream>
using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d", &n, &m);
    for (int i = 1; i < n; i++) scanf("%d", &a[i]); // 从1开始是方便处理边界问题

    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 - r]);
    }
    return 0;
}

这个还是相对比较简单的，但是这种处理边界的方法，还是值得学习的。

将一维扩展到二维道理也是相通的

6. 二维前缀和

重点是公式，稍微在脑海里模拟一下二维数组即矩阵的状态就能知道代码要怎么写了

输入一个 n 行 m 列的整数矩阵，再输入 q个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

#include <iostream>

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++) // 从1, 1开始的原因还是方便表达
    {
        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 ++)
            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；
}

7. 最后一部分 差分

差分就是前缀和的逆运算

输入一个长度为 n 的整数序列。

接下来输入 mm个操作，每个操作包含三个整数 l,r,c表示将序列中 [l,r][l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

#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()
{
    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]);

    while (m --)
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c); // 得到加c后的数组
    }

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

7. 差分矩阵

构造原矩阵a的差分矩阵b （ps：差分的问题都不用考虑构造，构造就相当于进行差分一遍）

一维的差分是对一段进行操作，而二维的话则是对一个子矩阵进行操作。

利用公式之后，本来需要枚举的就变成了O(n)就变成了O(1），这是多么令人快乐的啊。

而对于初始构造，也可以看成是一个单位为1的矩阵进行操作。

#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[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    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;
        cin >> 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 - 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 ++)
            cout << b[i][j] << ' ';
        cout << endl;
    }   

    return 0;

}

差分是一种思路，对数组进行差分后，能够替代枚举的过程，提高效率，也是很典型的利用空间换时间的做法，在拆完之后，即做完有所有操作后，需要将数组还原成完整状态。