XCPC历险记第二章!带你玩转高精度、前缀和与差分!-创新互联

文章目录
  • 一、高精度剖析与例题讲解
    • 1.A+B(A,B位数很大,如1e6级别)
    • 2.A-B(A,B位数很大,如1e6级别)
    • 3.A*b(A的位数很大,如1e6级别;但b相较A很小,如b的值在1e6级别)
    • 4.A/b(A的位数很大,如1e6级别;但b相较A很小,如b的值在1e6级别
  • 二、前缀和、差分剖析与例题讲解
    • 二、1.前缀和
      • 二、1、1.前缀和的求法
      • 二、1、2.前缀和的作用
    • 二、2.二维前缀和
      • 二、2.1二维前缀和的作用
      • 二、2.1前缀和的求法
    • 二、3.差分
      • 二、4.二维差分

在这里插入图片描述

创新互联成都企业网站建设服务,提供成都网站制作、网站建设、外贸网站建设网站开发,网站定制,建网站,网站搭建,网站设计,成都响应式网站建设公司,网页设计师打造企业风格网站,提供周到的售前咨询和贴心的售后服务。欢迎咨询做网站需要多少钱:13518219792一、高精度剖析与例题讲解

高精度问题是一类处理长度(位数)很长的正整数的运算问题(以下均讨论非负数)。在学习具体的问题之前,我们首先要学习超长整数是如何存储的。对于超长整数,用某种数据类型来存储其实是行不通的,我们会把它的每一位存到数组里。在存储时,数组的小下标存低位,大下标存高位。比如若把123456(当然它不是超长整数,我们只是举个例子)存到数组里,那么就是6 5 4 3 2 1。这样做是因为加减乘除可能涉及到进位,而在数组尾部进行数据的修改是比较容易的。注意:不要混淆位数和数值!比如说,若一个数的数值<=10,那么它的取值范围是0-10;若一个数的长度<=10,那么它的取值范围是0-9999999999。
高精度问题主要分为以下几类:

1.A+B(A,B位数很大,如1e6级别)

让我们先来回忆一下竖式加法的流程:
在这里插入图片描述

这里的ti(i = 0,1,2,3)表示进位,因此ti = 0或1。我们可以发现,Ci = (Ai + Bi + ti)%10。因此要实现超长整数相加,只需要把数组对应位置的数以及进位数加起来再模10,就可以得到新数字的每一位。 那么就让我们来看看代码如何实现吧!
在这里插入图片描述

#include#includeusing namespace std;
//传引用,防止多开空间
vectoradd(vector&A,vector&B)
{vectorC;
    //保存进位
    int t = 0;
    for(int i = 0;iif(i//用字符串的形式读数,可以拿到每一位
    string a,b;
    //定义大小可变化的数组
    vectorA,B;
    cin>>a>>b;
    //由于读进来的形式是字符,因此为了拿到那一位,我们要减去偏移量,即字符0的ASCII码值。
    //此外,我们要把数据倒着读进数组。
    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');
    
    vectorC = add(A,B);
    //倒着打印
    for(int i = C.size()-1;i>=0;i--)    printf("%d",C[i]);
    
    return 0;
}

一定要好好看注释哦,作者想说的都在注释里啦!如果你感觉阅读本段代码有困难,不妨先看看这个——[
C++vector快速入门

2.A-B(A,B位数很大,如1e6级别)

数据的存储方式同上。那么相减的算法思想是怎样的呢?我们通过竖式计算图来观察一下:
在这里插入图片描述
我们可以发现,与加法不同的是减法需要借位。假设上一位借该位t(t=0或1),那么

>=0 不需要借位 那么直接减就可以 得到Ai - Bi - t
Ai - Bi - t
<0 那么需要借位,也就是+10,得到Ai -Bi - t + 10

在这里插入图片描述

#includeusing namespace std;
#include//判断是否有 A>=B
bool cmp(vector&A,vector&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
//这里已经保证A>=B了
vectorsub(vector&A,vector&B)
{vectorC;
    //由于已经保证A>=B,所以A.size()>=B.size()
    for(int i = 0,t = 0;i//t为0表示不借位,为1表示借位
        //与上面的高精度加法不同的是,这里的t不方便更新,所以我们应该把t定义在循环里面,这样方便每次循环的时候更新重置!
        t = A[i] - t;
        //防止越界
        if(i0,就应该赋t给C。那么把二者结合起来就是下面的写法:
        C.push_back((t+10)%10);
        
        if(t<0) t = 1;
        else    t = 0;
    }
    //若出现形如003这样的结果,把0去掉
    while(C.size()>1&&C.back()==0)  C.pop_back();
    
    return C;
}

int main()
{string a,b;
    cin>>a>>b;
        vectorA,B,C;
    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))
    {C = sub(A,B);
        for(int i = C.size()-1;i>=0;i--)    printf("%d",C[i]);
    }
    else
    {C = sub(B,A);
        printf("-");
        for(int i = C.size()-1;i>=0;i--)    printf("%d",C[i]);
    }
    
    
}
3.A*b(A的位数很大,如1e6级别;但b相较A很小,如b的值在1e6级别)

首先,我们应该明白人类是怎么计算乘法的~~举一个例子看看吧!

**由于高精度乘法要把a看作整体,所以这里的相乘步骤与我们熟悉的逐位相乘略有不同,但原理是一样的:
在这里插入图片描述
我们可以看出乘法和加法的进位规则是类似的,下面让我们用代码来实现它吧!
在这里插入图片描述

#includeusing namespace std;
#includevectormul(vector&A,int&b)
{vectorC;
    int t = 0;
    //如果这里不加||t(即t!=0),会把结果的最高位(也就是C数组的最后一个元素)弄丢!
    //与加法不同的是,这里我们尝试把一个循环和一个判断(关于t的判断)放到一块了
    for(int i = 0;iif(i1&&C.back()==0)  C.pop_back();
    return C;
}
int main()
{string a;
    int b;
    cin>>a>>b;
    vectorA,C;
    
    for(int i = a.size()-1;i>=0;i--)    A.push_back(a[i] - '0');
    
    C = mul(A,b);
    
    for(int i = C.size()-1;i>=0;i--)    printf("%d",C[i]);
    
    return 0;
}
4.A/b(A的位数很大,如1e6级别;但b相较A很小,如b的值在1e6级别

我们还是先看看人类是怎么计算除法的。
在这里插入图片描述
(以下ri表示余数,初始r0设定为0)
我们可以发现,C3 = A3/b,r1 = (A3 % b)*10+A2,C2 = r1/b,r2 = (r1%b)*10+A3,C3 = r2/b,r3 = (r2%b)*10+A4,C4 = r3/b。
那么如何用代码实现这一过程呢?
在这里插入图片描述

#includeusing namespace std;
#include#include

vectordiv(vector&A,int&b,int&r)
{vectorC;
    //r为余数,初始值为0
    r = 0;
    for(int i = A.size()-1;i>=0;i--)
    {r = r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    //翻转数组
    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;
    
    vectorA;
    for(int i = a.size()-1;i>=0;i--)  A.push_back(a[i] - '0');
    
    int r = 0;
    vectorC;
    C = div(A,b,r);
    
    for(int i = C.size()-1;i>=0;i--)  printf("%d",C[i]);
    cout<

说明1:与加、减、乘不一样的是,除法的运算是从最高位开始的。那么按道理来说,我们并不需要把超长整数倒着存进数组里。但是一道题目中往往加减乘除混杂,为了统一,我们仍然采用倒着存进数组倒着打印的方式。而也正因为如此,div函数中i要从A.size-1开始,即倒着读。那么得到的C数组也要翻转。
说明2:通过前面四个例子的分析,我们可以注意到,对于某个变量k,若在循环中写成k = f(k)(这里f(k)是关于k的表达式),那么其实是一种递推!

二、前缀和、差分剖析与例题讲解 二、1.前缀和

前缀和是一个数组中前i项的和,记作Si。若一个数组为:a1,a2,a3,a4,……那么Si = a1 + a2 + a3 + …… + ai。

二、1、1.前缀和的求法

观察可知,Si = S(i-1) + ai。(记S0 = 0,便于处理边界)。

二、1、2.前缀和的作用

前缀和可以用来计算数组中一段数据的和。例如要求数组中【l,r】区间的和,我们可以用Sr - S(l - 1)。
接下来让我们看看具体的代码实现吧!
在这里插入图片描述

#includeusing namespace std;

const int N = 1e6+10;

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]);
    
    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;
}
二、2.二维前缀和

二维前缀和是一个矩阵某点左上角全部元素(包括该点)的和。例如有某个m*n矩阵A,那么(i,j)点的前缀和S(i,j)= a(1,1)+a(1,2)+……+a(1,j)+……+a(i,j)。在解决前缀和相关问题时,我们不妨把“和”看作“面积”,这样会直观一些。

二、2.1二维前缀和的作用

二维前缀和可以用来计算矩阵某一个区域内所有数据的和。例如:
在这里插入图片描述
那么从(i1,j1)到(i2,j2)的所有数据的和为:
S = S(i2,j2)- S(i1,j2 - 1)- S(i2,j1 - 1)+ S(i1 - 1,j1 - 1)(因为左上角的小区域被减了两次,所以要加回来)

二、2.1前缀和的求法

观察图可知,S(i,j)= S(i - 1,j)+ S(i,j-1)- S(i-1,j-1)(因为被加了两次,所以要减掉)+ a(i,j)。
有了上面的了解,我们就可以来看看代码模板了。
在这里插入图片描述

#includeusing namespace std;

const int N = 1010;

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

int main()
{//注意:若不给数组初始化,默认全部元素为0
    scanf("%d%d%d",&n,&m,&q);
    //注意:这里要从i=1,j=1开始!因为a数组下标从1开始会更方便些
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            scanf("%d",&a[i][j]);
    //注意:这里也要从i=1,j=1开始!这样i-1、j-1以后才能从零开始
    //迭代求前缀和
    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;
            
}
二、3.差分

差分是前缀和的逆运算。设已经有一个数组a1,a2,a3,a4……,这个数组的差分是指这样一个数组:它的前缀和为原数组。那么我们很容易就可以构造出差分数组:b1 = a1,b2 = a2 - a1,b3 = a3 - a2,b4 = a4 - a3……但实际上这个构造并不重要,只要我们观念上知道有一个构造即可。
差分的方法在什么时候有用呢?比如说我们要执行这样的操作:把a数组中【l ,r】内的数全部加上某个常数c,如果运用差分,把查分数组中的bl + c,b(r+1) -   c,那么由于b是a的差分数组,【l,r】内的数就自动全加上c了。而对于数组a,我们可以这样看:它初始的时候所有值为0,然后我们赋值时每次插入。
接下来让我们看看例题和解答代码吧!
在这里插入图片描述

using namespace std;

const int N = 100010;

int n, m;
//b是差分数组
int a[N], b[N];
//让b[l] + c,b[r+1]-c
void insert(int l, int r, int c)
{b[l] += c;
    b[r + 1] -= c;
}

int main()
{scanf("%d%d", &n, &m);
    //a、b数组下标都从1开始即可,因为这里没有边界条件
    for (int i = 1; i<= n; i ++ ) scanf("%d", &a[i]);
    //构造差分数组。由于最开始a、b数组中的元素全为0,因此最开始的时候b就是a的差分数组。那么对于每个新生成的a【i】,b【i】应该有相应的偏移。而对于b的某一项先-a【i】,后一项+a【i+1】,恰好能满足前缀和。,
    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);
    }
    //更新b数组,使得b数组变成自己的前缀和数组
    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;
}
二、4.二维差分

矩阵a(ij)的差分矩阵是指这样的矩阵:a(ij)中的项是差分矩阵前缀和。那么借助一维差分和二维前缀和的经验,我们知道可以这样初始化差分矩阵b(假若要把阴影部分加上c)(这里我们不必考虑b的具体构造):
在这里插入图片描述
那么b应该作相应的变化:b(x1,y1)+= c,b(x2+1,y1)-= c,b(x1,y1+1)-= c ,b(x2+1,y2+1)+= c。为什么这样修改以后a中阴影部分会+c呢?、因为对于a数组,靠近往右往下方向是相加的b数组中的项增大的方向,那么我们只要给区域左上角的b(x1,y1)加上c,那么x1,y1以后的a中的项(即右下角的项)都会加上c。然后在阴影之外我们不希望a中数据有变化,所以只要做相应的调整即可。
在这里插入图片描述

#includeusing namespace std;

const int N = 1010;

int n, m, q;
//a是原数组,b是差分数组
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,使得它作为自己的前缀和数组
            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;
}

好啦!以上便是本篇文章的全部内容。这里的代码均出自Acwing闫学灿大佬之手,这是他的主页:
Acwing闫学灿
博主给代码加上了注释和自己的思考总结。祝大家学习愉快!

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章标题:XCPC历险记第二章!带你玩转高精度、前缀和与差分!-创新互联
文章链接:http://pwwzsj.com/article/ioose.html