代码模板2---基础算法(高精度/前缀和/差分)

一、高精度

1.高精度加法

string读入到vector中(注意前面存储的是较低位，是为了方便vector在back进行加一位)

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);//让下面的默认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 % 10);
        t /= 10;//是否需要进位在此体现
    }
 
    if (t) C.push_back(t);//看最后是否会有进位
    return C;
}

2.高精度减法

整体的思路: ①若A>=B,直接计算A-B ②若A

注：①(t+10)%10 是为了当t<0的时候（是需要借一位的）当t>0的时候%10不变！---统一解 

       ②最后一步勿忘记去除高位0(减法会将高位消成0)

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    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;                //当t<0，表示需要借位,t=1
        else t = 0;                      
    }
 
    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除高位0!!!
    return C;
}

加法和减法统一是：①先处理t(让t对下一位产生影响)

                                ②如果没超过b的size，才进行操作add or sub

                                ③然后进行res的push_back

                                ④最后进行t的改变 

3.高精度乘法

几个细节见注释(循环条件t+中间处理步骤+去除前导零)

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
 
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )//注意t不为0的时候,也需要进行循环!
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);            //将res进行push_back
        t /= 10;                        //最后更新t
    }
 
    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导零
 
    return C;
}

4.高精度除法

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)//余数用引用返回
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )//从末尾(即较高的数位开始处理)
    {
        r = r * 10 + A[i];//每处理下一个顺位的时候,需要先乘上10
        C.push_back(r / b);//res进行push_back整除后的值
        r %= b;            //更新r(余数),下一轮需要重复第一行
    }
    reverse(C.begin(), C.end());//数的高位在vec的低位
    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0
    return C;
}
//高精度除以低精度

一般是从最高位开始处理的，%余下的数乘10+下一位的数字进行下一步操作 

二、前缀和、差分

1.前缀和

注意：a0=0包括二维数组也是从零开始，这样公式就可以统一了，al+...+ar=Sr-S(l-1)

当left=1，right=x的时候,利用S[x]-S[1-1]=S[x]-S[0]=S[x]-0统一公式.

        ①一维数组的前缀和

公式：

        S[i] = a[1] + a[2] + ... a[i]
        a[l] + ... + a[r] = S[r] - S[l - 1]

int l , r;
cin >> l >> r;
cout << S[r] - S[l - 1];

        ②二维数组的前缀和

公式：

S[i, j] = 第i行j列格子左上部分所有元素的和
①以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
        S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

     tips:同样的真正的下标从1开始,这样统一公式，上述公式即可变成(x2,y2)到(x1-1,y1-1)

②初始化S矩阵:
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]

int a[N][N] , S[N][N];    // N由实际需要确定其值
 
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 ++){
        S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j];
    }

int S[N][N];    // N由实际需要确定其值
int x1 , x2 , y1 , y2;
scanf("%d%d%d%d",&x1 , &y1 , &x2 , &y2);
//计算子矩阵的和
printf("%d\n" , S[x2][y2] - S[x2][y1-1] - S[x1 - 1][y2] + S[x1-1][y1-1]);

2.差分

 ①一维差分

板子：

        给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>q[i];
    for(int i=1;i<=n;i++)
        insert(i,i,q[i]);//构造差分矩阵
        
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }//修改差分矩阵
    for(int i=1;i<=n;i++)
        q[i]=q[i-1]+b[i];//求前缀和
    
    for(int i=1;i<=n;i++)
        cout<" ";
    return 0;
}

②二维差分

板子：

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
        S[x1, y1] += c,

        S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c,

        S[x2 + 1, y2 + 1] += c

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()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>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]);//构造差分矩阵b
    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++)  
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];//求二维前缀和
        
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<" ";
        cout<
    }
    return 0;
}

补充:     有关insert构造差分矩阵的含义