高精度/前缀和/差分
-
高精度
-
存储方式:
- 整数的长度一般小于1e6
- 大整数的每一位存储到数组里
- 存储时低位在前,高位在后,方便进位
-
高精度加法
- 每一位相加Ai + Bi + t, t表示进位取值0/1,逢十进一
-
模板:
//存储方式 string a, b;//a = "123456" vector<int> A, B;//A = [6,5,4,3,2,1] 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'); //加法 vector<int> add(vector<int> &A, vector<int> &B){ vector<int> C; int t = 0; for(int i = 0; i < A.size() || i < B.size(); ++ i){ if(i < A.size()) t += A[i]; //t = A[i] + B[i]; if(i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if(t) C.push_back(1); return C; } //逆序输出 for(int i = C.size() - 1; i >= 0; -- i) cout << C[i];
-
高精度减法
- 每一位相减Ai - Bi - t, t 表示借位取值0/1
-
模板:
//判断是否有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]; } //减法,要保证A > B 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]; //t = A[i] - B[i] - t C.push_back((t + 10) % 10); if(t < 0) t = 1; else t = 0; } //删除前导零 while(C.size() > 1 && C.back() == 0) C.pop_back(); } //输出 if(cmp(A, B)){ auto C = sub(A, B); for(int i = C.size() - 1; i >= 0; -- i) cout << C[i]; }else if(a == b) cout << 0; }else{ auto C = sub(B, A); //交换位置 for(int i = C.size() - 1; i >= 0; -- i) cout << C[i]; }
-
高精度乘法
- A * b ,b<=10000, len(A) <= 1e6 , 乘的时候将b看作整体,而不是一位一位的乘
- 一般是很大的数乘上一个小的数
-
模板:
string a; int b; vector<int> A; for(int i = a.size() - 1; i >= 0; -- i) A.push_back(a[i] - '0'); //乘法 vector<int> mul(vector<int> &A, vector<int> &B){ vector<int> C; for(int i = 0, t = 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();//去前导零(b==0时) return C; }
-
高精度除法
- 一般是高精度的整数除以一个低精度的整数
- 除法可以正序存储,为了一致性,依然逆序存储
-
模板:
vector<int> div(vector<int> &A, int b, int &r){//r是余数,C存储商 vector<int> C; r = 0; for(int i = A.size() - 1; i >= 0; -- i){//从高位开始算 r = r * 10 + A[i]; C.push_back(r % b); t /= b; } reverse(C.begin(), C.end()); while(C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
-
-
前缀和
-
一维前缀和
- Sn = a1 + a2 + a3 + a4 + ....+ an
- Sn = Sn-1 + an
- O(1) 求区间和
- 前缀和思想很重要!!
-
模板:
//初始化 for(int i = 1; i <= n; ++ i) s[i] = s[i - 1] + a[i]; //求和 cout << s[r] - s[l - 1];
-
二维前缀和
- 基于容斥原理
-
模板:
//初始化 for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; //区间求和 左上角(a, b) 右下角(c, d) cout << s[c][d] - s[a - 1][d] - s[c][b - 1] + s[a - 1][b - 1];
-
-
差分
- 差分与前缀和互为逆运算
- O(1) 区间修改
- 差分的前缀和即为原数组
-
一维差分
-
模板:
void add(int l, int r, int c){ //在区间[l, r] 上加上c b[l] += c; b[r + 1] -= c; } //差分数组初始化,初始化就相当于在[i, i] 区间上加上a[i] //所以初始化就与区间修改操作统一了 for(int i = 1; i <= n; ++ i) add(i, i, a[i]); //差分数组初始化 for(int i = 1; i <= n; ++ i) b[i] = a[i] - a[i - 1]; //求原数组,直接利用b数组 for(int i = 1; i <= n; ++ i) b[i] += b[i - 1];
-
-
二维差分
-
模板:
//在以(x1, y1)为右上角(x2, y2)为左上角的矩形区域加上c void add(int x1, int y1, int x2, int y2, int c){ d[x1][y1] += c; d[x2 + 1][y1] -= c; d[x1][y2 + 1] -= c; d[x2 + 1][y2 + 1] += c; } //求原数组 for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) d[i][j] += d[i - 1][j] + d[i][j - 1] + d[i - 1][j - 1];
-