(1)算法思想(分治)：
先确认分界点：一般选为左端点l或者右端点r或者中间点(l+r)/2
调整区间：使分界点左侧的数都小于等于分界点，右侧的数都大于等于分界点
递归处理左右两侧
(2)代码实现思路：
循环实现分界点调整区间操作，设置两个指针i,j分别指向数组的首尾，将两个指针的内容的大小与分界点比较，当左指针内容小于分界点，左指针右移，当右指针内容大于分界点，右指针左移，否则先交换两个指针的内容，再向中间靠拢。如果两个指针相遇，则退出循环。通过递归将每一个分界点完成调整区间操作。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n;
int a[N];
void quick_sort(int a[],int l,int r)
{
if(l>=r) return;
int x=a[l],i=l-1,j=r+1;
while(i<j)
{
do i++; while(a[i]<x);//当左指针内容小于分界点的值右移
do j--; while(a[j]>x);//当右指针内容小于分界点的值左移
if(i<j) swap(a[i],a[j]);//当左指针大于等于，右指针小于
//等于，交换两指针的内容，又因为
//do循环所以两指针同时向中间移动
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) cin>>a[i];
quick_sort(a,0,n-1);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}(1)算法思想：
先确认分界点：一般选中间点(l+r)/2
排序：递归排序分界点左侧和右侧
归并：将两侧已经排序完成的数组合并成一个数组
(2)代码实现思路：
先以中间点为分界点，将整个数组分为左右两侧，然后依次递归处理，设置左右指针分别指向左侧的第一个元素和右侧的第一个元素，直到左右指针相等时返回。对于每一次递归都要进行合并操作，即设置一个新的数组，循环依次比较左右指针，将较小的数放到新数组中，直到某个指针到达终点，再将未放置完的一侧数字依次放入新数组后面。最后将新数组依次复制到递归数组中。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n;
int a[N],tmp[N];
void merge_sort(int a[],int l,int r)
{
if(l>=r) return;
int mid=(l+r)/2;
merge_sort(a,l,mid),merge_sort(a,mid+1,r);//递归排序左侧和右侧
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) tmp[k++]=a[i++];//如果左指针小，则放入新数组中
else tmp[k++]=a[j++];//否则右指针内容放入新数组中
}
while(i<=mid) tmp[k++]=a[i++];//如果左侧有剩余，则将剩余部分放入新数组中
while(j<=r) tmp[k++]=a[j++];//如果右侧有剩余，则将剩余部分放入新数组中
for(int i=l,j=0;i<=r;i++,j++) a[i]=tmp[j];//将新数组的内容复制到递归数组中
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
merge_sort(a,0,n-1);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
}(1)算法思想：
模板一
确认中间值：根据已排序完成的数组，选择中间点mid=(l+r+1)/2，假设小于待查找数x的范围为左区间，右侧为大于待查找数x的范围为右区间（这里与我之前学的思维有点差异：我之前学的是用x跟mid的内容比较，y总讲的是mid的内容和x比较，直接看代码可能更好理解一些~）
条件判断：判断mid是否满足左区间性质（即x>=a[mid]），如果满足则说明mid在左区间,即x在mid右侧（更新区间为[mid,r]，l=mid），否则x在mid左侧（更新区间为[l,mid-1],r=mid-1）
可以看出，当有多个x出现在数组中时，一定是l先锁定x的位置（因为相等时更新的是l），然后如果下次q[mid]（当l和r不重合时，mid一定在l右侧）再一次小于等于（重点是等于,即若l不等于r时，当再次找到x时，这时候的x一定在上一个x（位置为l）的右侧）依旧更新l，因此最终l是在x出现的最后一个位置。
因此该模版查找的是x出现的最后一个位置，因为相等时更新l，而l不断向右移动（mid向上取整,即mid=(l+r+1)/2）。
模板二
确认中间值：根据已排序完成的数组，选择中间点mid=(l+r)/2，假设小于待查找数x的范围为左区间，右侧为大于待查找数x的范围为右区间
条件判断：判断mid是否满足右区间性质（即x<=a[mid]），如果满足则说明mid在右区间,即x在mid左侧（更新区间为[l,mid]，r=mid），否则x在mid右侧（更新区间为[mid+1,r],l=mid+1）
可以看出，当有多个x出现在数组中时，一定是r先锁定x的位置（因为相等时更新的是r），然后如果下次q[mid]（当l和r不重合时，mid一定在r左侧）再一次大于等于（重点是等于,即若l不等于r时，当再次找到x时，这时候的x一定在上一个x（位置为r）的左侧）依旧更新r，因此最终r是在x出现的第一个位置。
因此该模版查找的是x出现的第一个位置，因为相等时更新r，而r不断向左移动（mid向下取整，即mid=(l+r)/2）。
(2)代码实现思路：
设置两个指针l,r分别指向区间两端，待查找的数为x。
模板一（寻找满足左区间条件的数）
设置mid为mid=(l+r+1)/2，如果满足a[mid]<=x，则令l=mid，否则令r=mid-1,循环结束时l=r。
模板二（寻找满足右区间条件的数）
设置mid为mid=(l+r)/2，如果满足a[mid]>=x，则令r=mid，否则令l=mid+1,循环结束时l=r。
(3)代码实现：
#include <iostream>
using namespace std;
const int N=1e6+10;
int n;
int a[N];
int m,x;
int main() {
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
while(m--)
{
cin>>x;
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]!=x) cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r+1)/2;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}(1)算法思想：（使用上面哪种模板都可以）
确认中间值：根据已排序完成的数组，选择中间点mid=(l+r)/2，假设小于待查找数x的范围为左区间，右侧为大于待查找数x的范围为右区间
条件判断：判断mid是否满足右区间性质（即x<=a[mid]），如果满足则说明mid在右区间,即x在mid左侧（更新区间为[l,mid]，r=mid），否则x在mid右侧（更新区间为[mid,r],l=mid）
(2)代码实现思路：
设置两个指针l,r分别指向区间两端，待查找的数为x。
设置mid为mid=(l+r)/2，如果满足a[mid]>=x，则令r=mid，否则令l=mid,循环结束时r-l<1e-6(或者更小的数)。
(3)代码实现：
#include <iostream>
using namespace std;
double x;
int main()
{
cin>>x;
double l=0,r=x;
while(r-l>1e-6)
{
double mid=(r+l)/2;
if(mid*mid>=x) r=mid;
else l=mid;
}
cout<<l;
return 0;
}
简介：由于存在一些位数极多的数（如10^6个位数的大整数），它们在c++中无法用一个已知数据类型表示，所以需要运用新的表示方法，一般采用开辟一个存储各位数字的数组，倒序存入大整数每一位的数字（方便进位）。
(1)算法思想：
进位设置：设置进位Ti，T0=0
判断溢出：如果Ai+Bi+Ti-1大于10，则将本位的进位Ti设置为1
计算本位和:将本位与进位的和对10进行取余运算，即可计算出本位和
(2)代码实现思路：
首先输入两个字符串，将两个字符串倒序存入两个vector数组中。设置进位t并初始化为0，将其与每一位做加法，将此时的t对10取余，即为本位和，再对10做除法，即为本位产生的进位。当i大于每一个数组的位数时退出循环，最后判断最高位的进位是否存在，若不为0则在末尾添加1。
(3)代码实现：
#include <iostream>
#include <vector>
using namespace std;
string a,b;
vector<int> A,B;
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];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(1);
return C;
}
int main() {
cin>>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(A,B);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}
(1)算法思想：
判断被减数A和减数B关系：如果A<B，计算-（B-A）
借位设置:如果低位产生借位则，Ti为1，初始为0
判断每一位被减数Ai与减数Bi关系：如果Ai>Bi，直接减;如果Ai<=Bi, 减完加10。
计算本位和:将两数相减的结果再减去借位即为本位和
(2)代码实现思路：
首先比较被减数A和减数B的大小关系：设置布尔类型的函数，如果A的位数不等于B的位数，则返回位数做差后的结果；否则比较每一位，如果不相等，返回该位两数做差后的结果。若函数返回true，则不变，否则交换A,B顺序，并先输出“-”。
再创建减法运算的函数：设置借位t并初始化为0，让被减数Ai减去借位t，再与减数Bi相减，将此时的t加10后再对10取余即可实现对本位结果正负两种情况的处理。
最后，处理输出多余0的情况，如果输出的数组最后一位为0，则丢弃。
(3)代码实现：
#include <iostream>
#include <vector>
using namespace std;
string a,b;
vector<int> A,B;
bool cmp(vector<int> &A,vector<int> &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;//如果相等不输出-
}
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=0;
else t=1;
}
while(C.size()>1&&C.back()==0) C.pop_back();//C.size()>1保证如果结果就是0那么就不删除最后一位
return C;
}
int main() {
cin>>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--) cout << C[i];
}else{
auto C = sub(B,A);
cout<<"-";
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
}
return 0;
}
(1)算法思想：
与正常手算略有不同：把乘数当成一个整体看待。
进位:设置进位Ti，初始为0，本位向高位的进位等于本位乘积除10（注：这里的本位是指被乘数，因为将乘数看成一个整体）
计算本位和:将两数相乘的结果对10取余即为本位和（由于乘数是正常大小的数所以可以直接计算）
(2)代码实现思路：
将乘数其与被乘数每一位做乘法，结果记为t，将此时的t对10取余，即为本位和，再对10做除法，即为本位产生的进位。最后判断最高位的进位是否存在，若不为0则在末尾添加此时的进位（这里可以写进循环判断条件中，若t不为0，则加入最终数组中）。
(3)代码实现：
#include <iostream>
#include <vector>
using namespace std;
int b;
vector<int> A;
string a;
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;//因为循环条件加上了t所以这里要重新判断一下条件是否符合
C.push_back(t%10);
t/=10;
}
return C;
}
int main()
{
cin>>a>>b;
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--) cout<<C[i];
return 0;
}(1)算法思想：
与之前的计算不同：除法是从高位开始做运算。
进位:设置余数r，初始为0，本位的余数是上一位的余数乘10加上本位的数字再对除数取余
计算本位商:本位的商是余数乘10加上本位的数字再除以除数
(2)代码实现思路：
循环从高位，即被除数数组的末尾开始。将每一位产生的余数除以除数即为本位的商，再将余数对除数取余即为本位产生的余数，每一位使用的余数是将上一位的余数乘10在加上本位的数。最终要考虑处理输出多余0的情况，如果输出的数组最后一位为0，则丢弃。
(3)代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N =1e6+10;
int n,b,r;
vector<int> A;
string a;
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;
}
int main()
{
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--) cout<<C[i]<<endl;
cout<<r;
return 0;
}(1)算法思想：
创建一个前缀和数组S，通过S[i]=S[i-1]+a[i]计算数组a中前i个数的和，注意i从1开始。通过前缀和数组可以很快计算出数组a中某一段区间的和，如求l,r之间的和，就可通过计算S[r]-S[l-1]得出。
(2)代码实现：
#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N],s[N];
int n,m;
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}(1)算法思想：（观察左上部分）
将二维数组看成一个矩形，创建一个前缀和数组S，因此S[i][j]就是数组a在（i,j）左上部分所有元素之和，可以通过S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j]计算每一个位置的左上部分和。通过该前缀和数组可以很快计算出数组a中某块矩形区域的元素和，如求(x1,y1)（小）和(x2,y2)（大）之间的和，就可通过计算S[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]得出。
(2)代码实现：
#include <iostream>
using namespace std;
const int N = 1e3+10;
int a[N][N],s[N][N];
int n,m,q;
int main() {
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[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]+a[i][j];
while(q--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}(1)算法思想：
假设一个差分数组b,使得该数组满足b[i]=a[i]-a[i-1]（a[0]初始为0），因此a[i]等于差分数组前面i个元素的和。所以当对原数组a的[l,r]区间内的元素都加上c时，可以通过对b[l]加c，此时由于区间内a数组的所有元素都等于差分数组前面i项的和，因此在a[l]之后的所有元素都加上了c。此时要想达到目的，只需要在r项之后每一项都减去c即可，因此只需将b[r+1]减去c即可使得a[r]之后所有元素都减去了c.
创建差分数组也可以通过类似的方法建立，如在差分数组区间（1,1）插入a[1]即可实现在b[1]位置插入a[1],同时b[2]位置处为-a[1],依此类推，即可完成建立。
(2)代码实现：
#include <iostream>
using namespace std;
const int N=1e6+10;
int a[N],b[N];
int n,m;
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) insert(i,i,a[i]);
while(m--)
{
int l,r,c;
cin>>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++) cout<<b[i]<<" ";
return 0;
}
(1)算法思想：(观察右下部分)
将二维数组看成一个矩形，对于a[i][j]而言，它就是左上部分所有差分矩阵元素的和。因此，对照一维差分可以知道，对差分矩阵b[i][j]做变化就是对数组a在（i，j）右下部分做变化，差分矩阵的创建也可以通过类似的操作得出。即，若想使得矩形内(x1,y1)（小）与(x2,y2)（大）间的矩形元素统一发生变化，则可通过b[x1][y1]+=c，b[x2+1][y1]-=c，b[x1][y2+1]-=c,b[x2+1][y2+1]+=c实现
(2)代码实现：
#include <iostream>
using namespace std;
const int N=1e3+10;
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() {
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>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,x2,y1,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[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++)
cout<<b[i][j]<<" ";
cout<<endl;
}
return 0;
}
因篇幅问题不能全部显示，请点此查看更多更全内容