算法基础（2）

第一章 基础算法

高精度

算法4：高精度（只有C++需要），一般有四种情况：

1. 两个大整数相加 A + B，A、B的位数 $\le 10^6$；
2. 两个大整数相减 A - B，A、B的位数 $\le 10^6$；
3. 一个大整数乘以一个小整数 A * a，A的位数$\le 10^6$，a$\le 10000$；
4. 一个大整数除以一个小整数 A / a，A的位数$\le 10^6$，a$\le 10000$；

首先要考虑的是一个大整数如何存储？方法是可以将其中的每一位保存在一个数组中，为了方便运算，让a[0]存数字的个位，a[1]存数字的十位……依次存高位。如数字以string类型输入a = "123456"，用vector<int>来存储，A=[6,5,4,3,2,1]。

（1）加法

两个数组的加法运算就是来模拟人工手算的过程，从个位开始逐位相加，逢十进一。

#include<iostream>
#include<vector>
using namespace std;

//C = A + B
vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    if(A.size() < B.size())  return add(B, A);
    
    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;
}

int main()
{
    string a, b;
    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 i = b.size() - 1; i >= 0; i--)  B.push_back(b[i] - '0');
    
    vector<int> C = add(A, B);
    
    for(int i = C.size() - 1; i >= 0; i--)  printf("%d", C[i]);
    return 0;
}

还可以在空间上做进一步的优化，即进行压位处理，数组中的每一个元素不止存放数字的一位，而是多位。（不常用）

#include <iostream>
#include <vector>

using namespace std;

const int base = 1000000000;

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 % base);
        t /= base;
    }

    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, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (a[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            A.push_back(s);
            s = j = 0;
            t = 1;
        }
    }
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (b[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            B.push_back(s);
            s = j = 0;
            t = 1;
        }
    }

    auto C = add(A, B);

    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
    cout << endl;

    return 0;
}

（2）减法

两个数组的减法运算也是来模拟人工手算的过程，从个位开始逐位相减，不够就向前一位借1，加10。

算法的思路：

• 如果A$\ge$B，就计算$A - B$；如果A$<$B，就计算 $-(B - A)$。
• 在每一位上，若$A_i-B_i-t \ge 0$，就计算$A_i-B_i-t$；若$A_i-B_i-t < 0$，就计算$A_i-B_i+10-t $，其中$t$代表借位。

#include<iostream>
#include<vector>
using namespace std;

//判断是否有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;
}
//C = A - B
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;   //进位
    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;   //当前的t小于0，需要借位
        else t = 0;
    }
    
    while(C.size() > 1 && C.back() == 0)  C.pop_back();   //去掉前导0
    return C;
}

int main()
{
    string a, b;
    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 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;
}

（3）乘法

也是模拟手算乘法，区别是：逐位相乘时是乘以整个被乘数b。

#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() || 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();  //当被乘数是0时，要将结果的前导0去掉
    
    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）除法

同样的思路，模拟手算的过程，注意区别：除法是从最高位开始除的。

#include<iostream>
#include<vector>
#include<algorithm>

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;
    }
    //除法中C先存的是数字的高位，与定义的先存低位相反，要先翻转一下
    reverse(C.begin(), C.end());
    //去掉前导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');  //这里一定要记得减去'0'
    
    int r;
    auto C = div(A, b, r);
    
    for(int i = C.size() - 1; i >= 0; i--)  printf("%d",C[i]);
    cout << endl << r << endl;
    
    return 0;
}

前缀和，差分

算法5：前缀和，差分

前缀和：设一个数组$a_1,a_2,a_3,\dots,a_n$，（注意下标从1开始），定义其前缀和为$S_i=a_1+a_2+\dots+a_i$，规定$S_0=0$。

• 如何求前缀和$S_i$：for遍历即可；
• 前缀和的作用：可以方便地求出序列中某一段的和，如求下标区间$[l,r]$内的元素的和，即可用$S_r-S_{l-1}$，时间复杂度为$O(1)$。

#include<iostream>
using namespace std;

const int N = 100010;
int n, m;
int a[N], s[N];

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

前缀和也可以扩展到二维，求区间和$\to$求子矩阵和。用$S_{ij}$表示左上角的子矩阵的和。如下图若要求以$(x_1,y_1)$为左上角，以$(x_2,y_2)$为右下角的子矩阵的和，那就可以转化成求：

$$S_{x_2y_2}-S_{x_2y_1-1}-S_{x_1-1y_2}+S_{x_1-1y_1-1}$$

如何求子矩阵和$S_{ij}$：两层for遍历i,j，

$$S_{ij}=S_{i-1j}+S_{ij-1}-S_{i-1j-1}+a_{ij}$$

主要的思想就是容斥原理。

#include<iostream>
using namespace std;

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++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][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;
}

差分是前缀和的逆运算，设一个数组$a_1, a_2, \dots, a_n$，现构造一个数组$b_1,b_2,\dots, b_n$，使得$a_i=b_1+b_2+\dots+b_n$，即$a$数组的元素是$b$数组的前缀和，$b$数组的元素是$a$数组的差分。则有：

$$\begin{align*} b_1 &= a_1 \\ b_2 &= a_2-a_1\\ b_3 &= a_3-a_2\\ &\dots \\ b_n &= a_n-a_{n-1} \end{align*}$$

差分的作用：

• 若有$b$数组，就可以通过求前缀和的方法求得原数组$a$，时间复杂度$O(n)$。
• 若要对$a$数组下标为$[l,r]$区间的一段元素都加上$c$，则要$O(n)$的时间复杂度；若考虑改动$b$数组，那只要改变两个元素，即让$b_l+c$，让$b_{r+1}-c$，则只要$O(1)$的时间复杂度，这样由数组$b$得到的数组$a$的下标为$[l,r]$的一段就都加上了$c$。
• 那若有了数组$a$，如何得到数组$b$：可以假设数组$a$初始全部是0，依次在区间[1,1]加上$a_1$，在区间[2,2]加上$a_2$，……，在区间[n,n]加上$a_n$，即转换到对数组$b$的操作。

#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]);
        insert(i, i, a[i]);    //求得数组b
    }
    while(m--)
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    for(int i = 1; i <= n; i++)
    {
        b[i] += b[i-1];   //求数组b的前缀和
        printf("%d ", b[i]);
    }
    return 0;
}

差分也有二维的形式，原矩阵元素$a_{ij}$，差分矩阵元素$b_{ij}$，使得$a_{ij}$是差分矩阵$b_{ij}$的前缀和。

其作用也可由上面的一维差分类比过来：给矩阵$a$的某一个子矩阵（左上角为$(x_1,y_1)$，右下角为$(x_2,y_2)$）中的元素全都加上一个数$c$，可以转化成：

$$\begin{align*} b_{x_1y_1} &+=c\\ b_{x_2+1y_1} &-=c\\ b_{x_1y_2+1} &-=c\\ b_{x_2+1y_2+1} &+=c \end{align*}$$

#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]);
            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-1][j] + b[i][j-1] - b[i-1][j-1];
                printf("%d ", b[i][j]);
            }
            printf("\n");
        }
    return 0;
}