Basic Agorithm ( TWO ).
发布日期:2022-02-24 01:06:47
浏览次数:11
分类:技术文章
本文共 7753 字,大约阅读时间需要 25 分钟。
basic algorithm 2
高精度算法
在高精度算法中,需要用一个 string 来存储高精度数据, 然后将其倒置放到一个vector中,方便操作.
至于为什么要将其倒置存放到一个vector中,原因如下: 当我们做加法和乘法的时候 , 会产生进位,这个时候需要增加数字 ,而据数组的特性所知,在数组的末尾添加一个数字比在数组的开头添加一个数字要容易的多 . 所以当我们存储数字的时候 , 要把其个位存放到数组的头部 , 也就是我们所说的倒置存储.高精度加法:
模版:
// 大整数类加法#include#include #include using namespace std;const int maxn = 1e6 + 10;// 第一种写法:vector add_01(vector A, vector B){ vector C; if(A.size() < B.size()) add_01(B,A); // 判断A 长还是B长 防止到最后一位时还叠加 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 = t/10; } if(t) C.push_back(t); return C;}// 第二种写法:vector add_02(vector A, vector B){ vector C; int t = 0; for(int i = 0;i < A.size() || i < B.size();i++) { if(i < A.size()) t += A[i]; if(i < B.size()) t += B[i]; C.push_back(t%10); t = t/10; } if(t) C.push_back(t); return C;}int main(){ ios::sync_with_stdio(false); string a , b; cin >> a >> b; vector A , B; 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') ; auto C = add_02(A,B); for(int i = C.size()-1;i >= 0;i--) printf("%d",C[i]); return 0;}
高精度减法
模版:
// 对于给定的两个正整数 , 计算其差值#include#include #include using namespace std;// 判断 A 是否 大于等于 Bbool cmp(vector A, vector B){ if(A.size() != B.size()) return A.size() > B.size(); else { for(int i = A.size() - 1;i >= 0;i--) if(A[i] != B[i]) return A[i] > B[i]; return true; }}/*bool cmp(vector A, vector B){ if(A.size() > B.size()) return true; else if(A.size() == B.size()) { for(int i = A.size() - 1;i >= 0;i--) if(A[i] > B[i]) return true; else if(A[i] == B[i]) continue; else return false; return true; } else return false;}*/// 对于要改变实参的函数 传参时用引用较好vector sub(vector &A,vector &B){ vector 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; else t = 0; } // 去掉前导零 但如果要保留个位上的0 while(C.size() > 1 && C.back() == 0) C.pop_back(); return C;}int main(){ string a , b; cin >> a >> b; vector A , B; 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)) { 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;}
高精度乘法:
模版:
#include#include #include using namespace std;// 第一种做法:/*vector mul(vector A,int b){ vector 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; } return C;}*/// 第二种做法:vector mul(vector A,int b){ vector C; int t = 0; // for(int i = 0;i < A.size();i ++ ) { t += A[i] * b; C.push_back(t % 10); t /= 10; } while(t) { C.push_back(t % 10) ; t /= 10; } return C;}int main(){ string a ; int b; cin >> a >> b; vector 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;}
高精度除法:
除法与其他三则运算不同的一点是从高位开始除,所以除完之后需要用reverse 函数进行逆置.
模版:// 高精度 除法:#include#include #include #include using namespace std;vector div(vector A,int b,int &r){ vector C; r = 0; for(int i = A.size() - 1;i >= 0;i -- ) { r = r*10 + A[i]; // 注意! 这里是除以 b 不是除以 10 C.push_back(r / b); r %= b; } reverse(C.begin(),C.end()); while(C.size() > 1 && C.back() == 0) C.pop_back(); return C;}int main(){ string a; int b , r; vector A; cin >> a >> b; for(int i = a.size() - 1;i >= 0;i -- ) A.push_back(a[i] - '0') ; 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;}
差分与前缀和
对于差分与前缀和 时间复杂度都是由 O(n)->O(1)
前缀和:
在初始化原数组的时候,注意下标要从1开始,留一个位置 ,防止造成边界问题. s0 = 0
作用: 快速地计算出数组中某一段数的和模版:
#includeusing namespace std;//一般来说 全局变量、静态变量处于数据区,默认初始化为0 const int maxn = 1e6 + 5; int arr[maxn]; int temp[maxn];int n , m;int main(){ scanf("%d %d",&n,&m); // 防止数据量过大超时选择使用 scanf输入 或者关闭ios的同步流用 cin 输入亦可 for(int i = 1;i <= n;i ++ ) scanf("%d",&arr[i]); temp[0] = 0; for(int i = 1;i <= n;i ++ ) temp[i] = temp[i - 1] + arr[i]; while(m--) { int l , r; scanf("%d %d",&l,&r); printf("%d\n",temp[r] - temp[l-1]); } return 0;}
子矩阵的前缀和
模版:
给定一个矩阵 ,给定两个点的坐标,求这两个点所包含的矩阵中的所有元素的和 Code:#includeusing namespace std;const int N = 10010;int arr[N][N] , s[N][N]; int n , m, q;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", &arr[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] + arr[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[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); } return 0;}
差分:
差分是一种与前缀和相对的策略,可以当作求前缀和的逆运算.
对于原数组 a1 a2 … an 构造 b数组 使得 ai = b1 + b2 +… + bi 作用: 区间修改 (也可用线段树)模版:
给定一个数组, 可对该数组任意区间进行操作修改, 求进行m次操作后的数组各个元素. code:#includeusing namespace std;const int maxn = 10010;int a[maxn] , b[maxn];int n , m;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]); // 构造差分数组 b for(int i = 1;i <= n;i ++ ) Insert(i,i,a[i]); // m 次修改操作 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]; for(int i = 1;i <= n;i ++ ) printf("%d ",b[i]); return 0;}
差分矩阵:
与一维差分和二维前缀和类似,初始化:由一维类推.
构造可以通过区间修改来完成 , 从而达到 修改的统一. 作用: 可以给矩阵的一个子矩阵的所有元素进行统一修改. 模版: 给定一个矩阵,可以对该矩阵的任意子矩阵进行m次修改操作,在 进行 m次操作后 打印输出修改后的矩阵Code:
#includeusing namespace std;const int N = 1010;int a[N][N] , b[N][N];int n , m , q;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; 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]; // 打印输出经过修改后的原数组 for (int i = 1;i <= n;i ++ ) { for(int j = 1;j <= m;j ++ ) printf("%d ",b[i][j]); cout << endl; } return 0;}
转载地址:https://blog.csdn.net/weixin_45877540/article/details/108292524 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月16日 20时56分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
单片机的几种数字滤波算法
2019-04-29
用单片机控制导弹?
2019-04-29
各种滤波器合集!
2019-04-29
国产CPU深度研究报告(干货,110页)
2019-04-29
在电路中,耦合是什么?有哪些方式?
2019-04-29
变局之际,聊聊物联网的过去、现在和未来
2019-04-29
缺货涨价很久的MCU的国产和国外厂家汇总!(80家)
2019-04-29
单片机6年想转嵌入式Linux ,不知如何下手?
2019-04-29
拆解 | 某平台19元的儿童电话手表,究竟怎么做到的?
2019-04-29
五一好礼70份免费送:示波器、开发板、焊台等!
2019-04-29
2纳米芯片问世!芯片性能要起飞?!
2019-04-29
ARM Cortex系列那么多处理器,该怎么区分?
2019-04-29
知乎:学计算机的女生都怎么样了?
2019-04-29
华为重磅反击,鸿蒙来了!
2019-04-29
常用电子接口大全,遇到不认识的,就翻出来对照辨认!
2019-04-29
芯片IC附近为啥要放0.1uF的电容?
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录。
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(上)
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(下)
2019-04-29