一、高精度运算&＃xff08;都是正数&＃xff09;

1、高精度加法&＃xff08;大数&＃43;大数)

2、高精度减法&＃xff08;大数-大数)

3、高精度乘法&＃xff08;大数*小数&＃xff09;

4、高精度除法&＃xff08;大数/小数&＃xff09;

二、前缀和

1、一维前缀和

2、二维前缀和&＃xff08;求小矩阵的和&＃xff09;

三、差分

1、一维差分

2、二维差分

---

1、高精度加法

模板:

#include
#include
#include
using namespace std;
const int N&＃61;1e6&＃43;10;
vector add(vector &A,vector &B)
{int t&＃61;0;vector C;for(int i&＃61;0;i&＃61;1)C.push_back(t);return C;//返回的类型是vector的
}
int main()
{string a,b;vectorA,B;//A,B两个容器cin>>a>>b;for(int i&＃61;a.size()-1;i>&＃61;0;i--)//a.size()字符串的长度A.push_back(a[i]-&＃39;0&＃39;);//将字符串逆序存入,把值加到B的末尾for(int i&＃61;b.size()-1;i>&＃61;0;i--)B.push_back(b[i]-&＃39;0&＃39;);vector C&＃61;add(A,B);int len&＃61;C.size();//最后结果的长度for(int i&＃61;len-1;i>&＃61;0;i--)//逆序放入也要逆序输出cout<}

2、高精度减法

模板

#include
#include
#include
using namespace std;
//先比较输入的两个数的大小
bool cmp(string a,string b)
{if(a.length()!&＃61;b.length())return a.length()>b.length();for(int i&＃61;0;ib[i];}return 1;//两个值相等
}
vector sub(vector &A,vector &B)
{int t&＃61;0;vector C;for(int i&＃61;0;i&＃61;0)t&＃61;0;elset&＃61;1;}//清除前导0while(C.size()>1&&C.back()&＃61;&＃61;0)//直到最后剩下一个数为0时就不能在删了C.pop_back();//把最后一个数删掉return C;
}
int main()
{string a,b;cin>>a>>b;vectorA,B;for(int i&＃61;a.size()-1;i>&＃61;0;i--)A.push_back(a[i]-&＃39;0&＃39;);for(int i&＃61;b.size()-1;i>&＃61;0;i--)B.push_back(b[i]-&＃39;0&＃39;);vector C;//判断A,B的大小&＃xff0c;决定正负号if(cmp(a,b)){C&＃61;sub(A,B);for(int i&＃61;C.size()-1;i>&＃61;0;i--)cout<&＃61;0;i--)cout<}

3、高精度乘法&＃xff08;大数*小数&＃xff09;

&＃xff08;1&＃xff09;思路&＃xff1a;这里是直接把较小的那个数当成一个整体来算的&＃xff0c;妙&＃xff01;&＃xff01;&＃xff01;

&＃xff08;1&＃xff09;模板

#include
#include
#include
using namespace std;
vector mul(vector &A,int b)
{int t&＃61;0;vector C;for(int i&＃61;0;i1&&C.back()&＃61;&＃61;0)//删除前导0C.pop_back();//把容器A中的最后一个删掉return C;
}
int main()
{string a;int b;vector A;cin>>a>>b;for(int i&＃61;a.size()-1;i>&＃61;0;i--)A.push_back(a[i]-&＃39;0&＃39;);vector C&＃61;mul(A,b);for(int i&＃61;C.size()-1;i>&＃61;0;i--)cout<}

4.高精度除法

模板

#include
#include
#include
#include
using namespace std;
vector div(vector &A,int b,int &r)//r余数
{vector C;//这里要逆序计算&＃xff0c;因为前面是逆序存放的&＃xff0c;但是由于考虑//到加减乘除可能在一起混合使用的情况&＃xff0c;为了避免输入的麻烦&＃xff0c;就把除法也逆序输入了 。//但是除法我们本来就是顺着来的。for(int i&＃61;A.size()-1;i>&＃61;0;i--){r&＃61;r*10&＃43;A[i];C.push_back(r/b);//这里存放到c里的答案是顺序的r%&＃61;b;}reverse(C.begin(),C.end());//虽然C已经是顺序排放了&＃xff0c;但是输出的时候是逆序&＃xff0c;所以//把C转置一下while(C.size()>1&&C.back()&＃61;&＃61;0)C.pop_back();return C;
}
int main()
{string a;int b;vector A;cin>>a>>b;for(int i&＃61;a.size()-1;i>&＃61;0;i--)A.push_back(a[i]-&＃39;0&＃39;);int r&＃61;0;//一开始余数0vector C&＃61;div(A,b,r);for(int i&＃61;C.size()-1;i>&＃61;0;i--)cout<}

二、前缀和

1、一维前缀和&＃xff1a;公式&＃xff0c;sum[i]&＃61;sum[i-1]&＃43;a[i];下标i从1开始取。

2.二维前缀和

思路&＃xff1a;

题目&＃xff1a;https://www.acwing.com/problem/content/798/(求子矩阵的和&＃xff09;


#include
using namespace std;
const int M&＃61;1010;
int a[M][M],sum[M][M];
int main()
{int n,m,q;scanf("%d%d%d",&n,&m,&q);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){scanf("%d",&a[i][j]);}}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){//前缀和;减去多出来的两个小正方形&＃xff0c;在加上被多减去的小正方形sum[i][j]&＃61;sum[i][j-1]&＃43;sum[i-1][j]-sum[i-1][j-1]&＃43;a[i][j];//矩阵前缀和}}while(q--){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//小矩阵的和&＃61;sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]&＃43;sum[x1-1][y1-1]printf("%d\n",sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]&＃43;sum[x1-1][y1-1]);}return 0;
}

三&＃xff0c;差分

1、一维差分

&＃xff08;1&＃xff09;思路&＃xff1a;令B1&＃61;A1,B2&＃61;A2-A1,...Bn&＃61;An-A(n-1),则An&＃61;B1&＃43;B2&＃43;...&＃43;Bn&＃xff0c;称数组B为数组A的差分&＃xff0c;数组A为数组B的前缀和。

作用&＃xff1a;如果想要给数组A[l,r]里的每个数加上c,那么我们可以对b数组进行操作&＃xff0c;只需要b[l]&＃43;&＃61;c&＃xff08;可以使数组a从l往后的所有数加上c&＃xff09;,b[r&＃43;1]-&＃61;c&＃xff08;因为只需要给[l,r]里的数加上c&＃xff0c;所以还要把r之后的数减去c&＃xff09;,即可完成给数组a[l,r]里的每个数加上c。

题目&＃xff1a;797. 差分 - AcWing题库

#include
using namespace std;
const int M&＃61;100010;
int a[M],b[M];
void insert(int l,int r,int c)//构造差分数组
{//我们只需要给[l,r]里的数加上c,所以只需要在l这里加就可给后面的数也加上。b[l]&＃43;&＃61;c;b[r&＃43;1]-&＃61;c;
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&a[i]);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)insert(i,i,a[i]);//这里构造差分数组时可看成在[i,i]里加上a[i]while(m--){int l,r,c;scanf("%d%d%d",&l,&r,&c);insert(l,r,c);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)b[i]&＃43;&＃61;b[i-1];//求差分数组的前缀和for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)printf("%d ",b[i]);//每个b[i]对应的是a[i]的值return 0;
}

2、二维差分

思路&＃xff1a;它是先把原数组一一插入到差分数组b中&＃xff0c;然后在差分数组上面进行修改&＃xff0c;最后通过求差分数组的前缀和来得到原数组。差分数组的前缀和与原数组的下标是一一对应的。二维差分&＃xff1a;使a[i][j]是数组b[i][j]的前缀和,即b[i][j]是a[i][j]的差分数组。所以可以通过修改一个b[i][j](还未求前缀和前的)的值就可以影响其后面所有的值。

题目&＃xff1a;https://www.acwing.com/problem/content/800/

#include
using namespace std;
const int M&＃61;1010;
int a[M][M],b[M][M];
void insert(int x1,int y1,int x2,int y2,int c)//构造二维差分
{b[x1][y1]&＃43;&＃61;c;b[x2&＃43;1][y1]-&＃61;c;b[x1][y2&＃43;1]-&＃61;c;b[x2&＃43;1][y2&＃43;1]&＃43;&＃61;c;
}
int main()
{int n,m,q;scanf("%d%d%d",&n,&m,&q);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){scanf("%d",&a[i][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);//先插入数&＃xff0c;把插入的数加到差分数组b里的某一个元素就行了}//最后再求前缀和for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)b[i][j]&＃43;&＃61;b[i][j-1]&＃43;b[i-1][j]-b[i-1][j-1];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){printf("%d ",b[i][j]);}printf("\n");}return 0;
}

题目&＃xff1a;

1、https://codeforces.com/problemset/problem/1455/B

思路&＃xff1a;可发现sum&＃61;1&＃43;2&＃43;3&＃43;4&＃43;...&＃43;k&＃xff0c;当在第一步后退时sum-2,在第2步后退时,sum-3,于是可发现如果在其中的任意一步选择了后退总可以有sum-x(x>1)。所以只需要比较sum与n之间的关系即可。

#include
using namespace std;
int main()
{int t,n;cin>>t;while(t--){cin>>n;int sum&＃61;0,k&＃61;0;//k来记录走的第几步while(sum}

2、https://codeforces.com/problemset/problem/1541/B
题意&＃xff1a;给定一个整数数组&＃xff0c;找出满足下标i 思路&＃xff1a;首先可发现i&＃43;j的取值范围在[3,2*n-1],即a[i]*a[j]的范围为[3,2*n-1],所以找出在这个范围里的所有因子x,x即为a[i],于是可得a[j]。再判断a[i],a[j]是否是存在的且a[i]*a[j]&＃61;&＃61;i&＃43;j,同时注意我们在找因子的时候会出现a[i]&＃61;&＃61;a[j]的情况&＃xff0c;所以还要加上a[i]!&＃61;a[j]这个条件&＃xff08;题目要求&＃xff09;。
这道题是先由乘积结果再来求出这两个数的&＃xff0c;只要确定了其中一个数&＃xff0c;那么另一个数也可确定。

#include
#include
#define M 200005
using namespace std;
int main()
{int t,n,a[M];scanf("%d",&t);while(t--){//memset(a,0,sizeof(a));for(int i&＃61;0;i}

3、https://codeforces.com/problemset/problem/466/A
思路&＃xff1a;比较m张票单独买的价钱a*m和一起买的价钱b的大小来决定是要分开买还是一起买&＃xff0c;如果一起买较便宜的话就计算出能一起整买多少份m,然后再把剩余的不足m张票的来比较是单独买还是以m张的团购价格来买便宜&＃xff08;一开始忽略了这一步&＃xff09;。
 

#include
using namespace std;
int main()
{int n,m,a,b,sum;cin>>n>>m>>a>>b;if(m*a<&＃61;b){sum&＃61;n*a;}else{sum&＃61;n/m*b&＃43;(n%m*a>b?b:n%m*a);}cout<}

4、Problem - 363B - Codeforces

思路&＃xff1a;用前缀和来记录每个点和它自身之前的所有高度之和,再遍历查找连续长度为k的最小长度&＃xff0c;由sum[i]-sum[i-k]可得到在不同地方连续k个长度的总和&＃xff0c;把最小长度的下标保存起来。

#include
using namespace std;
int sum[150005];
int main()
{int n,k,x;scanf("%d%d",&n,&k);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){cin>>x;sum[i]&＃61;sum[i-1]&＃43;x;}int min&＃61;sum[k],index&＃61;1;for(int i&＃61;k&＃43;1;i<&＃61;n;i&＃43;&＃43;){if(min>sum[i]-sum[i-k]){min&＃61;sum[i]-sum[i-k];index&＃61;i-k&＃43;1;}}printf("%d\n",index);return 0;
}