C++ 常用算法模板整理【蓝桥杯】

文章目录前言一、基础数据结构与算法二、图论 / 搜索算法三、数论算法四、动态规划算法总结前言为方便日常刷题与竞赛使用本文整理了常用的 C 算法模板基础算法、搜索、图论、数论及动态规划等核心内容。一、基础数据结构与算法1.求区间和用前缀和#includeiostream#includevectorusingnamespacestd;constintN1e510;inta[N],s[N];// 数组a前缀和数组sintmain(){intn5;for(inti1;in;i){cina[i];}// 计算前缀和s[i] a[1] a[2] ... a[i]for(inti1;in;i){s[i]s[i-1]a[i];}intl2,r4;// 区间[l,r]的和s[r]-s[l-1]couts[r]-s[l-1]endl;return0;}2.找答案有单调性用二分// 在有序数组a中找到第一个 x的位置intlower_bound(inta[],intn,intx){intl0,rn-1;while(lr){intmidlr1;//等价于(lr)/2防溢出if(a[mid]x){rmid;}elselmid1;}returnl;}二、图论 / 搜索算法3.迷宫连通块用深度优先搜索走到底constintMAXN105;intdx[]{-1,1,0,0};// 上下左右四个方向intdy[]{0,0,-1,1};boolvis[MAXN][MAXN];// 访问标记数组// 从(x,y)出发DFS遍历连通块voiddfs(intx,inty){vis[x][y]true;// 标记已访问for(inti0;i4;i){intnxxdx[i];intnyydy[i];// 边界判断未访问if(nx0nxMAXNny0nyMAXN!vis[nx][ny]){dfs(nx,ny);}}}4.求最短路径最少步数用广度优先搜索#includequeueconstintMAXN105;intdx[]{-1,1,0,0};intdy[]{0,0,-1,1};boolvis[MAXN][MAXN];// 从(sx, sy)出发BFS求最短路径无权图voidbfs(intsx,intsy){queuepairint,intq;q.push({sx,sy});vis[sx][sy]true;while(!q.empty()){auto[x,y]q.front();q.pop();for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx0nxMAXNny0nyMAXN!vis[nx][ny]){vis[nx][ny]true;q.push({nx,ny});}}}}5.判断连通朋友圈用并查集constintN1e510;intfa[N];// 父节点数组// 初始化每个元素的父节点是自己voidinit(intn){for(inti1;in;i){fa[i]i;}}// 查找x的根节点路径压缩intfind(intx){if(fa[x]!x){fa[x]find(fa[x]);}returnfa[x];}// 合并x和y所在的集合voidunite(intx,inty){intfxfind(x);intfyfind(y);if(fx!fy){fa[fy]fx;}}三、数论算法6.素数质数多用埃式筛constintMAX_N100005;vectorintprime;boolis_prime[MAX_N];// 埃氏筛核心函数voidEra(){for(inti2;iMAX_N;i){is_prime[i]true;}for(inti2;iMAX_N;i){if(is_prime[i]){prime.push_back(i);}if((longlong)i*iMAX_N){continue;}for(intji*i;jMAX_N;ji){is_prime[j]false;}}}7.大指数幂取模用快速幂// 计算(a^b)%modlonglongqpow(longlonga,longlongb,longlongmod){longlongres1;a%mod;//先取模避免溢出while(b0){if(b1){resres*a%mod;//二进制末位为1乘入结果}aa*a%mod;//底数平方b1;//指数右移一位}returnres;}四、动态规划算法8.选或不选不限容量用0-1背包#includealgorithmusingnamespacestd;constintN1010;intw[N],v[N];//w[i]第i个物品的重量v[i]第i个物品的价值intdp[N];//dp[j]容量为j时的最大价值//n物品数量C背包总容量intbag01(intn,intC){//初始化dp数组为0fill(dp,dpC1,0);for(inti1;in;i){//逆序遍历防止重复选同一个物品for(intjC;jw[i];j--){dp[j]max(dp[j],dp[j-w[i]]v[i]);}}returndp[C];}9.最长递增子序列用LIS模板#includealgorithmusingnamespacestd;constintN1005;inta[N],dp[N];// 求数组a的最长递增子序列长度intLIS(inta[],intn){intans1;for(inti0;in;i){dp[i]1;// 每个元素自身长度为1for(intj0;ji;j){if(a[j]a[i]){dp[i]max(dp[i],dp[j]1);}}ansmax(ans,dp[i]);}returnans;}总结以上是常用算法的核心 C 实现模板熟练掌握并灵活运用这些基础代码能够有效提升编程效率与解题速度。