里面云智能建站,凡客软件,网店美工工资,河北网站优化公司说明 本篇文章只给出代码模板#xff0c;以及自己对该模板的理解。如果想看正确的算法思路#xff0c;可以移步AcWing官网看详情。链接#xff1a;常用代码模板1——基础算法 - AcWing 如有理解错误#xff0c;欢迎大家批评指正。
简单算法模板
一、排序
1.1 快… 说明 本篇文章只给出代码模板以及自己对该模板的理解。如果想看正确的算法思路可以移步AcWing官网看详情。链接常用代码模板1——基础算法 - AcWing 如有理解错误欢迎大家批评指正。
简单算法模板
一、排序
1.1 快速排序模板
void quick_sort(int q[],int l,int r){//q是传入的数组[l,r]是需要排序的范围if(lr) return;int i l-1,j r1,x q[lr1];while(ij){do i;while(q[i]x);do j--;while(q[j]x);if(ij) swap(q[i],q[j]);}quick_sort(q,l,j),quick(q,j1,r);
}
1.2 归并排序
int tmp[N];//需要开一个临时数组tmp[],N至少跟传入的q[]数组的范围一致
void merge_sort(int q[],int l,int r){if(lr) return;int mid rl1;merge_sort(q,l,mid),merge_sort(q,mid1,r);int k 0,i l,j mid1;while(imidjr){if(q[i]q[j]) tmp[k]q[i];else tmp[k]q[j];}while(imid) tmp[k]q[i];while(jr) tmp[k]q[j];for(int il,j0;ir;i,j) q[i]tmp[j];
}
二、 二分
2.1 整数二分模板1
bool check(int x){//check函数检查x是否满足某种性质//根据题意完善check()函数
}
//区间被划分为[l,mid],[mid1,r]
int bsearch1(int l,int r){while(lr){int midlr1;if(check(mid)) rmid;else lmid1;}return l;
}
2.2 整数二分模板2
bool check(int x){//check函数检查x是否满足某种性质//根据题意完善check()函数
}
//区间被划分为[l,mid-1],[mid,r]
int bsearch2(int l,int r){while(lr){int midlr11;if(check(mid)) lmid;else rmid1;}return l;
}
浮点数二分模板
bool check(double x){//check函数检查x是否满足某种性质//根据题意完善check()函数
}
double bsearch3(double l,double r){const double eps 1e-8;//定义精度如果题目要求精确到小数点后六位小数eps最好开到1e-8保险while(r-leps){double mid (lr)/2;if(check(mid)) r mid;else l mid;}return l;
}
三、高精度
3.1 高精度大数的存储
string a;cin a;//以字符串读入大整数
vectorint A;//使用vectorint A从个位往高位存储即逆序存储
for(int i a.size()-1;i0;i--) A.push_back(s[i]-0);
3.2 AB模板
//CAB,A0,B0
//C中还可用于引用变量常用于传参和定义别名
//如第6行代码若写成
//vectorint add(vectorint A,vectorint B){
//可能会爆内存并且会严重拖慢程序运行速度
vectorint add(vectorint A,vectorint B){//参数为大整数AB返回AB的vectorif(A.size()B.size()) return add(B,A);vectorint C;int t 0;//t表示进位for(int i 0;iA.size();i){tA[i];if(iB.size()) tB[i];C.push_back(t%10);t/10;}if(t) C.push_back(t);//如果最高位还有进位则放入C中return C;
}
3.3 A-B模板
//CA-B,A0,B0
vectorint sub(vectorint A,vectorint B){//参数为大整数AB返回A-B的vectorvectorint C;int t 0;//t表示借位for(int i 0;iC.size();i){tA[i]-t;if(iB.size()) t-B[i];C.push_back((t10)%10);//(t10)是为了防止t为负数导致取模后出现负数if(t0) t1;//有借位else t0;//没有借位}while(C.size()1C.back()0) C.pop_back();//去除前导零return C;
}
3.4 A*b模板
//CA*b,A0,b0
vectorint mul(vectorint A,int b){//参数为大整数A小整数b返回A*b的vectorvectorint C;int t 0;//t表示进位值区别于AB的进位t可能是很大的for(int i 0;iA.size()||t;i){if(iA.size()) tA[i]*b;C.push_back(t%10);t/10;}while(C.size()1C.back()0) C.pop_back();//去除前导零return C;
}
3.5 A/b模板
//A/bC...r,A0,b0
vectorint div(vectorint A,int b,int r){//参数为大整数A小整数br用于带回计算出的余数vectorint C;r 0;for(int i A.size();i0;i--){rr*10A[i];C.push_back(r/b);r%b;}reverse(C.begin(),C.end());//反转C方便去除前导零和输出while(C.size()1C.back()0) C.pop_back();//去除前导零return C;
}
四、前缀和、差分
4.1 一维前缀和模板
//如果我们要求数组a[]大量的子区间[l,r]的数之和
const int N 1e65;
int a[N],prefix[N];//preifx[]为前缀和数组
void solve(){int n;cin n;//有n个数1n1000000for(int i 1;in;i) cin a[i];//下标一定从1开始//计算前缀和for(int i 1;in;i) prefix[i]prefix[i-1]a[i];int q;cin q;//有q次询问while(q--){int l,r;cin l r;//[l,r]为询问区间//输出子区间[l,r]的数之和cout prefix[r]-prefix[l-1] endl;//endl - \n}
}
4.2 二维前缀和模板
//如果我们要求矩阵a[][]大量的子矩阵(a[x1][y1]和a[x2][y2]组成的子矩阵)的数之和
const int N 1e35;
int a[N][N],prefix[N][N];//prefix[][]为前缀和数组
void solve(){int n;cin n;//n行n列的矩阵1n1000for(int i 1;in;i) for(int j 1;jn;j) cin a[i][j];//下标从1开始//计算前缀和for(int i 1;in;i){for(int j 1;jn;j){prefix[i][j]prefix[i-1][j]prefix[i][j-1]a[i][j]-preifx[i-1][j-1];}}int q;cin q;//q次询问while(q--){int x1,y1,x2,y2;cin x1 y1 x2 y2;//子矩阵的范围//输出子矩阵数之和cout prefix[x2][y2]-preifx[x1-1][y2]-prefix[x2][y1-1]prefix[x1-1][y1-1] endl;//endl - \n}
}
4.3 一维差分模板
//如果我们要大量统一修改数组a[]的区间[l,r]的值使该区间的数都加上x并要我们输出最终修改后的数组
const int N 1e65;
int a[N],diff[N];//diff[]为差分数组
void solve(){int n;cin n;//有n个数1n1000000for(int i 1;in;i) cin a[i];//下标从1开始//计算差分数组for(int i 1;in;i) diff[i]a[i]-a[i-1];int q;cin q;//q次修改while(q--){int l,r,x;cin l r x;//[l,r]区间内的数都加xdiff[l]x,diff[r1]-x;}for(int i 1;in;i) a[i]a[i-1]diff[i];//构造修改后的数组a[]for(int i 1;in;i) cout a[i] \n[in];//遍历输出输出完最后一个数后输出换行
}
4.4 二维差分模板
//如果我们要大量统一修改矩阵a[][]的子矩阵(a[x1][y1]和a[x2][y2]形成的子矩阵)使该区间都加上x并要我们输出最终修改后的数组
const int N 1e35;
int a[N][N],diff[N][N];//diff[][]为差分数组
void update(int x1,int y1,int x2,int y2,int x){diff[x1][y1]x,diff[x21][y21]x,diff[x1][y21]-x,diff[x21][y1]-x;
}
void solve(){int n;cin n;//n行n列的矩阵1n1000for(int i 1;in;i) for(int j 1;jn;j) cin a[i][j];//下标从1开始//计算差分数组for(int i 1;in;i){for(int j 1;jn;j){update(i,j,i,j,a[i][j]);//计算其实就是每次修改一个1×1的小矩阵}}int q;cin q;//q次询问while(q--){int x1,y1,x2,y2;cin x1 y1 x2 y2;//子矩阵的范围//实现修改update(x1,y1,x2,y2,x);}//构造回最终修改后的矩阵a[][]for(int i 1;in;i){for(int j 1;jn;j){a[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1]-diff[i][j];}}//遍历输出,输出完一行后换行for(int i 1;in;i){for(int j 1;jn;j) cout a[i][j] \n[jn];}
}
五、双指针
5.1 双指针模板
bool check(int i,int j){//具体问题的逻辑
}
void solve(){for(int i 0,j0;in;i){while(jicheck(i,j)) j;//具体问题的逻辑}
}
//常见问题分类
// (1) 对于一个序列用两个指针维护一段区间
// (2) 对于两个序列维护某种次序比如归并排序中合并两个有序序列的操作
//上述分类大致都包含快慢指针和对撞指针等例题
六、位运算
情景1 求整数n的第k位二进制数字
情景1模板
int find(int n){return nk1;
}
void solve(){int n;cin n;//读入ncout find(n) endl;//调用函数并输出结果
}
情景2 求整数n的二进制表示中最低位的1的值
情景2模板
int lowbit(int n){//这个计算就被称为lowbit操作return n(-n);
}
//如求6的lowbit6表示二进制补码为(0……0110)即29个0110
//-6的补码为(1……1010)即29个1010
//而(0……0110)(1……1010) -- (0……0010)即结果的二进制为30个010转换为十进制的值为2
void solve(){int n;cin n;//读入ncout lowbit(n) endl;//调用函数并输出结果
}
七、离散化
7.1 离散化模板
vectorint alls;//存储所有待离散化的值
//使用vector排序去重(要求会默写)
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
// 二分求出x对应的离散化的值
int find(int x){//找到第一个大于等于x的位置int l0,ralls.size()-1;while (lr){int midlr1;if(alls[mid]x) rmid;else lmid1;}return r1;//映射到1,2,...,n
}
八、 区间合并
8.1 区间合并模板
// 将所有存在交集的区间合并
void merge(vectorPII segs){//PII-pairint,intpair存储的是左端点l和右端点r的二元组合并后的结果放回segsvectorPII res;sort(segs.begin(),segs.end());int st-2e9,ed-2e9;for(auto seg:segs){if(edseg.first){if(st!-2e9) res.push_back({st,ed});stseg.first,edseg.second;}else edmax(ed,seg.second);}if (st!-2e9) res.push_back({st, ed});segsres;
}
