首页 > 其他分享 >高精度+前缀和+差分

高精度+前缀和+差分

时间：2023-01-02 22:12:29浏览次数：44  
标签：10 前缀 高精度 int back 差分 vector size

高精度+前缀和+差分

高精度

高精度加法

  1. 大整数存储：将数字存到数组里，第一个位置存个位，第二个位置存十位......
  2. 从\(A_0+B_0\)开始算起，算个位，满十进一

易错点：

  1. 将数字存在字符串里面，然后倒序转换进数组
  2. 在函数内模拟整数各数位的加法，在十位的时候加上个位满十溢出的值，最后倒序输出即可

高精度加法算法模板：

// 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);

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

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

高精度减法

​ A3 A2 A1 A0

​ - B2 B1 B0

\(A >= B\) 计算 \(A - B\)

\(A < B\) 计算 \(- ( B - A )\)

\(t\) 表示是否借位

\(A_2 - B_2 - t >= 0\) $A_2 - B_2 - t $

\(A_2 - B_2 - t < 0\) $A_2 - B_2 + 10 - t $

注意点：

  1. 在\(cmp\)函数中最后要记得的返回true，因为判断的是是否 \(A >= B\)
  2. 不要忘记去除答案的前导0

高精度减法算法模板：

//判断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, 满足A >= B, A >= 0, B >= 0
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;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();	//去除前导0
    return C;
}

int main()
{
    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 j = b.size() - 1; j >= 0; j --) B.push_back(b[j] - '0');
	
    if(cmp(A, B))
    {
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i --) printf("%d",C[i]);
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i --) printf("%d",C[i]);
    }
    return 0;
}

高精度乘法

123 * 12

3 * 12 = 36 36 %10 = 6 36 / 10 = 3

2 * 12 + 3 = 27 27 % 10 = 7 27 / 10 = 2

1 * 12 + 2 = 14 14 % 10 = 4 14 / 10 = 1

0 * 12 + 1 = 1 1 % 10 = 1

1476

A5 A4 A3 A2 A1 A0

* b

进位：t

个位：A0 * b % 10 t = A0 * b / 10

十位：(A1 * b + t ) % 10 t = (A1 * b + t ) / 10

注意点：

  1. 注意一下进位的t，到最后可能已经运算完了但是t里面还存着首位的1，所以可以在最后加上去

    所以也可以在循环里面不考虑t，在循环结束后加上 if(t) C.push_back(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 ++ )
    {
        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;
}

高精度除法

1234 ➗ 11

r = 0 * 10 + 1 = 1 1 / 11 = 0 r = 1 % 11 = 1

r = 1 * 10 + 2 = 12 12 / 11 = 1 r = 12 % 11 = 1

r = 1 * 10 + 3 = 13 13 / 11 = 1 r = 13 % 11 = 2

r = 2 * 10 + 4 = 24 24 / 11 = 2 r = 14 % 11 = 2

r = 0 * 10 + 2 = 2 2 / 11 = 0 r= 2 % 11 = 2

1234 ➗ 11 = 112 ...... 2

A3 A2 A1 A0 ➗ b

r = 0 * 10 + A1 r / b = C3 r = r % b

r = r * 10 + A2 r / b = C2 r = r % b

注意点：

  1. 注意要reverse，以及头文件algorithm，这里是顺序求出答案存入数组的

高精度除以低精度算法模板：

// 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];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

前缀和与差分

一维前缀和

\(S[i] = a[1] + a[2] + ... a[i]\)

建议从a[1]开始存元素

预处理O(n) 询问O(1)

  1. 如何求\(S[i]\)
S[0] = 0;
for(int i = 1; i <= n; i ++)
    S[i] = S[i - 1] + a[i];
  1. 作用：可以快速求出原数组中一段数\([l,r]\)的和，
a[l] + ... + a[r] = S[r] - S[l - 1];

一维前缀和算法模板：

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

二维前缀和

a[i][j] 表示元素

S[i][j] 表示左上角矩形里面所有元素的和

a b c

d e f

g h i

\(a[2][2]-a[3][3]:s[3][3]-s[1][3]-s[3][1]+s[1][1]\)

那么要求以 \(a[x_1][y_1]\)和 \(a[x_2][y_2]\) 为顶点的矩形里面的元素的和，就是 \(s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-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];
    }
}
//询问
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 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]

一维差分

差分是前缀和的逆运算

由a[1] a[2] a[3] 构造 b[1] b[2] b[3] 数组，使得a[i] = b[1] + ... + b[i]， 也就是说 a[] 是 b[] 的前缀和

所以 b[1] = a[1] b[2] = a[2] - a[1] b[i] = a[i] - a[i - 1]

要给 [l , r] 之间的元素都加上c a[l] + c , a[ l + 1] + c ,, O(n)

差分：O(n) 构造差分数组，更改b[]，再求一遍前缀和，就可以得到a[]

差分O(n) 修改O(1)

a[] 是 b[] 的前缀和 将b[l] + c之后，a[l] 往后也会加上c，但是将a[r + 1] - c ， 就可以取消对于后面的元素的影响了

int q[maxn], b[maxn];
for(int i = 1; i <= n; i ++)    scanf("%d", &q[i]);
    
for(int i = 1; i <= n; i ++)    b[i] = q[i] - q[i - 1];		//求差分数组

scanf("%d%d%d", &l, &r, &c);
b[l] += c;
b[r + 1] -= c;
//进行增加操作

for(int i = 1; i <= n; i ++)    q[i] = b[i] + q[i - 1]; 	//前缀和求原数组

一维差分算法模板：

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

二维差分

原矩阵 \(a[i][j]\)

构造差分矩阵 \(b[i][j]\)

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;
}
//构建差分数组
for(int i = 1; i <= n; i ++)
{
    for(int j = 1; j <= m; j ++)
    {
        insert(i, j, i, j, q[i][j]);
    }
}
//将元素加上c
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 ++)
    {	
        q[i][j] = q[i - 1][j] + q[i][j - 1] - q[i - 1][j - 1] + b[i][j];
    }
}

二维差分算法模板：

给以(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

标签：10,前缀,高精度,int,back,差分,vector,size
From： https://www.cnblogs.com/xushengxiang/p/17020681.html

相关文章

  • 牛客训练(BIT+高精度)
    又是这类用BIT辅助计数的题。。这个显然满足要求的区间比不满足的要多太多，所以变成求不满足的。。。然后要先求总方案数，为这个不是很想在化了，反正O(n)求也可以的。。然后求......
  • 【LeeCode】14. 最长公共前缀
    【题目描述】编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ​​""​​。​​​​https://leetcode.cn/problems/longest-common-prefix......
  • 前缀和，差分
    前缀和，差分通俗理解前缀和听起来好高级啊，那么他究竟是什么啊？当询问一个区间[l,r]的和sum（忽略掉O(n)的暴力，它就发挥了大用处。基本的前缀和如下：s[i]=s[i-1]+a[i]......
  • 常用数据分析方法：方差分析及实现！
     Datawhale干货 作者：吴忠强，Datawhale优秀学习者，东北大学一个复杂的事物,其中往往有许多因素互相制约又互相依存。方差分析是一种常用的数据分析方法，其目的是通过数据分析......
  • 差分数组 前缀和数组
    小结：1、有数组d=[1,2,3,4,5,6]，对d[2]到d[4]之间的所有数加上3，变为d=[1,2,6,7,8,6]，那么差分数组也就从[1,1,1,1,1,1]变成了[1,1,4,1,1,-2]  Leetcode刷题笔记——差......
  • 本地化差分隐私随机扰动（回推）机制代码详解（K-RR）
    https://blog.csdn.net/ruiqu1650914788/article/details/127516602?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167245493516782427447943%2522%252C%2522......
  • P3128 [USACO15DEC]Max Flow P 树上点差分
    //题意：给出一棵树，现在有一操作：给出两点，将两点之间的路径都加1，最后统计整棵树中值最大的点是谁//思路：树上路径问题，树剖+线段树可以解决，但是因为只是简单的维护区间加减，用......
  • 差分好题
    Atcoder[ABC221D]Onlinegames难度：\(832\)标签：差分离散化\(\mathtt{blog}\)......
  • 【新生寒训】day 3 前缀和、差分
    【新生寒训】day3前缀和、差分学习这里：https://oi-wiki.org/basic/prefix-sum/后面也有附习题，可以看看✨然后上几道小题~P1387最大正方形；二分；货仓选址此外，可以做一......
  • D. Valiant's New Map (二位前缀和)
    D.Valiant'sNewMap题目大意给定一个二维数组，要求找到满足限制条件的最大正方形，限制条件为：正方形内所有元素都不小于该正方形的边长。解题思路显然可以二分答案，解题......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99