大学算法类竞赛的常用模板【自己总结+收录的】【c++版】

目录知识点常考【按照优先级多-少】常用模板【不是和知识点一一对应的因为有的知识点没有模板】知识点常考【按照优先级多-少】①前缀和数组和差分数组②递归和递推【能用for循环就别用其他循环和递归】③排序算法【sort()】贪心的思想局部最优④二分查找二分答案⑤暴力搜索【bfs和dfs】[bfs多练题就好dfs多练题看运气因为dfs可能超时]⑥记忆化的【bfs和dfs】也叫动态规划【dp】,将前面算出来或者遍历出来的值存起来后面需要用的时候直接用不用找了【难】常用模板【不是和知识点一一对应的因为有的知识点没有模板】1.冒泡排序【如果第一趟排序没有发生元素位置的交换说明这个数组的元素是有序的】【时间复杂度O(n²)】 void sort(vectorint stones){ for(int i0;istones.size()-1;i){ int temp10000; for(int j0;jstones.size()-1-i;j){ if(stones[j]stones[j1]){ tempstones[j]; stones[j]stones[j1]; stones[j1]temp; } } if(temp10000) break;//标记一下temp如果第一轮时temp没有被赋值说明数组原本就是有序的所以不需要再排序了可以直接输出。 } } 2.插入排序【时间复杂度O(n²)】 void crsort(vectorint a){ for(int i1;ia.size();i){ if(a[i]a[i-1]){ int tempa[i]; int j0; for(ji-1;j0;j--){ if(a[j]temp) a[j1]a[j]; if(a[j]temp){ a[j1]temp; break; } } if(j-1) a[0]temp; } } } 3.归并排序【时间复杂度为O(nlogn)的算法时间复杂度相当于最小了】 class Solution { void gb(vectorint a,int left,int mid,int right){ int n1mid-left1; int n2right-(mid1)1; int temp[n1n2]; for(int i0;in1;i){ temp[i]a[lefti]; } for(int j0;jn2;j){ temp[n1j]a[mid1j]; } int i0,jn1,kleft; while(in1 jn1n2){ if(temp[i]temp[j]) a[k]temp[i]; else a[k]temp[j]; } while(in1) a[k]temp[i]; while(jn1n2) a[k]temp[j]; } void gbsort(vectorint a,int left,int right){ if(leftright) return; int midleft(right-left)/2; gbsort(a,left,mid); gbsort(a,mid1,right); gb(a,left,mid,right); } public: vectorint sortArray(vectorint nums) { gbsort(nums,0,nums.size()-1); return nums; } }; 4.快速排序【时间复杂度O(nlogn)】 //过程模拟 // l r // 1 3 5 3 2 8 // i j class Solution { void swap(int x,int y){ int a0; ax; xy; ya; } int mid_yuansu(vectorint a,int l,int r){ int retl(rand()%(r-l1)); int xa[ret]; swap(a[l],a[ret]); int il,jr; while(ij){ while(ij a[j]x) j--; if(ij) swap(a[i],a[j]),i; while(ij a[i]x) i; if(ij) swap(a[i],a[j]),j--; } a[i]x; return i; } void kssort(vectorint a,int l,int r){ if(lr) return; int midmid_yuansu(a,l,r); kssort(a,l,mid-1); kssort(a,mid1,r); } public: vectorint sortArray(vectorint nums) { kssort(nums,0,nums.size()-1); return nums; } }; 5.深度优先搜索【dfs】 bool zhao[N]; bool dfs(int a,int b){ if(ab) return true; else zhao[a]true; for(int i0;iw[a].size();i){ if(!zhao[w[a][i]] dfs(w[a][i],b)){ return true; } } return false; } 6.清理残留的脏数据避免影响下一次的查找 memset(zhao,0,sizeof(zhao)); //查完一次后清除zhao[N]中的所有true和false,让他们都初始化为0避免影响下一次的查找 7.二分查找算法模板 a[mid]第一个 ≥ x 的数左边界【判断语句后是rmid所以midl(r-l)/2】【不需要1】 while (l r) { int mid l (r - l) / 2; // 不加1 if (a[mid] x) r mid; else l mid 1; } a[mid] 最后一个 ≤ x 的数右边界【判断语句后是lmid所以midl(r-l1)/2】【需要1】 while (l r) { int mid l (r - l 1) / 2; // 必须1 if (a[mid] x) l mid; else r mid - 1; } 8.判断一个数是否是质数的模板 【埃式筛选法欧拉进阶法】 例题求第2025个质数 #includebits/stdc.h using namespace std; const long long N1e5; bool is_zhishu[N]; vectorlong long zhishus; long long ret; void shi(long long n){//判断一个数是否是质数的模板 【埃式筛选法欧拉进阶法】 memset(is_zhishu,true,sizeof(is_zhishu)); is_zhishu[0]false; is_zhishu[1]false; for(long long i2;in;i){ if(is_zhishu[i]) zhishus.push_back(i); if(zhishus.size()2025){//如果此时已经有2025个质数了就输出zhishus[2024],数组的下标从0开始 retzhishus[2024]; break; } for(long long j0;jzhishus.size() i*zhishus[j]n;j){//欧拉进阶法【这个循环没有也能执行多这个循环可以让时间复杂度O( nlog(logn) )-O(n)】 is_zhishu[i*zhishus[j]]false; if(i%zhishus[j]0) break; } } } int main(){ long long n1e5; shi(n); coutret; return 0; } 9.洛谷1551亲戚【并查集模板题】【并查集函数 合并函数merge(x,y)查找函数finds(x)】 #includebits/stdc.h using namespace std; long long n,m,p; const int N1e410; long long fa[N]; long long finds(long long y){//找y的根节点 if(fa[y]y) return y; else return fa[y]finds(fa[y]); } void merge(long long x,long long y){//让x的根节点变成y的根节点 fa[finds(x)]finds(y); } int main(){ cinnmp; for(long long i1;in;i) fa[i]i; for(long long i1;im;i){ long long a0,b0; cinab; merge(a,b); } for(long long i1;ip;i){ long long a0,b0;cinab; if( finds(a)finds(b) ) coutYesendl; else coutNoendl; } return 0; } 10.判断一个数是不是2的次方 bool cifang_2(long long n){ return (n0 (n(n-1))0); } 当返回值为true是2的次方返回false不是2的次方