第零章技巧1.去除前导0while(C.size()1C.back()0) C.pop_back();2.字符串反转reverse(C.begin(),C.end());3.读取单个字符包括空格、换行char ch; ch cin.get(); cout ch;4.读取一整行string s; cin.ignore(); //忽略缓冲区一个字符换行 getline(cin,s);cin 和 getline 混用换行残留问题4.读取一整行substr (1, k)从下标 1 开始一共取出k 个字符第一章基础算法1.快速排序快速排序Quick Sort是一种高效的排序算法由C.A.R. Hoare在1960年提出其基本思想是分治法Divide and Conquer。具体步骤如下选择基准值从待排序序列中选取一个元素作为基准常选第一个或最后一个元素或中间元素划分序列将序列中小于等于基准的元素移到左边大于等于基准的元素移到右边。此时基准元素的位置就是它在最终排序中的正确位置。递归排序对基准左边和右边的子序列分别重复上述步骤直到子序列长度为1或0整个序列自然有序2.归并排序归并排序的核心思想是将一个数组分成两个子数组分别排序后再合并为一个有序数组。具体步骤如下分解将待排序数组递归地分成两部分直到每个子数组只包含一个元素。合并将两个有序子数组合并为一个有序数组。3.KMPKMP 算法用来解决模式串匹配问题。暴力匹配在失配时主串指针需要回退效率较差。KMP 分成两大步骤 第一步提前预处理模式串生成 next 数组。next 数组记录模式串每个位置前面那段子串最长相等前后缀的长度。第二步正式匹配。匹配过程中主串指不回退如果当前字符匹配失败不用把模式串从头开始比对依靠 next 数组把模式串指针跳到最长相等前后缀对应的位置复用前面已经匹配成功的重合部分继续和主串当前字符比较。第三章图论0.邻接表、邻接矩阵邻接矩阵适用于节点少的情况n1000const int N510; int g[N][N]; for(int i0;im;i){ int a,b,c;cinabc; g[a][b]min(g[a][b],c); g[b][a]min(g[b][a],c); }邻接表适用于节点多的情况n1e510const int N2e510; int e[N],ne[N],w[N],idx,h[N]; void add(int a,int b,int c){ e[idx]b,ne[idx]h[a],w[idx]c,h[a]idx; }1. Dijkstra求最短路使用范围所有边权重为非负数的图基本思路0 采用邻接表存边1 维护一个距离矩阵 dist[i] 表示 1 号点到第 i 号点的距离维护一个状态矩阵 st[i] 表示第 i 号点距离是否已经确定。2 建立一个小根堆距离节点编号表示点 i 距离 1 号点的距离每次操作找到距离 1 号点最短的点 i 将其标记为确定 更新点 i 的所有后续点若距离变短则加入堆中。memset(dis,0x3f,sizeof dis); priority_queuePII,vectorPII,greaterPII q; dis[1]0; q.push({0,1}); while(q.size()){ auto tq.top(); q.pop(); int jt.second; if(!st[j]){ st[j]true; for(int ih[j];i!-1;ine[i]){ int ke[i]; if(dis[k]dis[j]w[i]){ dis[k]dis[j]w[i]; q.push({dis[k],k}); } } } }2. bellman-ford求有边数限制的最短路使用范围求从 1 号点到 n 号点的最多经过 k 条边的最短距离基本思路0 直接采用结构体存边只要能遍历所有边就可以1 循环 k 轮访问每一条边(a-b)判断1-b和1-a-b若经过 a 到 b 可以更短则更新注意更新时要用上一次的距离进行更新保证每次循环只增加一条边。struct{ int a,b,c; }Edge[N]; dist[1]0; for(int i0;ik;i){ memcpy(last,dist,sizeof dist); for(int j0;jm;j){ int a,b,c; aEdge[j].a,bEdge[j].b,cEdge[j].c; dist[b]min(dist[b],last[a]c); } }3.spfa求最短路使用范围不存在负权回路基本可以替代Dijkstra背景在bellman-ford基础上进行优化因为每次只需要被更新的边去更新其他边就可以不需要遍历所有边。因此可以采用堆进行优化如果有边被更新那么放入堆中更新其他边。基本思路0 采用邻接表存边。1 维护一个状态数组 st[i] 表示当前节点 i 是否在队列中防止一个节点多次进入队列。2 从队列中取出一个节点并用这个节点去更新后续所有节点如果可以更新后续节点则将其更新如果后续节点不在队列中那么将该节点放入队列中。从队列中取出一个节点后应该将其标记为不在队列中。while(q.size()){ auto tq.front(); q.pop(); st[t]false; for(int ih[t];i!-1;ine[i]){ int je[i]; int disdist[t]w[i]; if(dist[j]dis){ dist[j]dis; if(!st[j]){ q.push(j); st[j]true; } } } }4.floyd求最短路使用范围求任意两点的最短路径基本思路动态规划f[k][i][j] 表示从 i 到 j 经过 前 k 条边的最短距离f[k][i][j] min( f[k-1][i][j] , f[k-1][i][k] f[k-1][k][j] ) ;for(int k1;kn;k) for(int i1;in;i) for(int j1;jn;j) f[i][j]min(f[i][j],f[i][k]f[k][j]);5.Prim求最小生成树背景和Dijkstra算法类似Dijkstra算法维护的时 1 到 i 的最短距离Prim算法维护的时 i 到已确集合的最短距离。基本思路 0 采用邻接表存边1 维护一个距离矩阵 dist[i] 表示 i 号点到已确定集合的最短距离维护一个状态矩阵 st[i] 表示第 i 号点是否已经确定。2 建立一个小根堆距离节点编号表示点 i 距离已确定集合的距离每次从堆中取出最小距离点如果该点未确认则将该点加入已确定集合并更新dist将dist被更新的点加入到队列中。while(q.size()){ auto tq.top(); q.pop(); int jt.second; if(st[j]) continue; st[j]true; cntdist[j]; for(int i1;in;i){ if(g[j][i]dist[i]){ dist[i]g[j][i]; q.push({dist[i],i}); } } }6.Kruskal求最小生成树背景采用并查集和贪心的思想基本思路0 可以用结构体或者用 pair 存边只要能对边排序就可以1 对边从小达到进行排序2 依次选择最小的边判断两端点是否在同一个集合块中如果不在将该边选上。sort(edge,edgem); for(int i0;im;i){ int a,b,c; aedge[i].second.first,bedge[i].second.second,cedge[i].first; if(find(a)!find(b)){ p[find(b)]find(a); cntc; n--; } } if(n1) coutcnt; else puts(impossible);7.染色法判定二分图背景二分图当且仅当不含奇数边基本思路1 染色可以使用1和2区分不同颜色用0表示未染色2 遍历所有点每次将未染色的点进行dfs, 默认染成1或者23 对于未染色的点对其染相反的颜色dfs未染色点的后继点对于已经染色的点判断颜色是否重复如果重复则返回 false如果该联通块都染色并且未重复则返回truebool dfs(int u,int c){ color[u]c; for(int ih[u];i!-1;ine[i]){ int je[i]; if(!color[j]){ if(!dfs(j,3-c)) return false; } else{ if(ccolor[j]) return false; } } return true; }8.匈牙利算法求二分图最大匹配基本思路看成男生女生找对象对于一个男生而言询问所有对他有好感的女生访问该女生是否有对象如果女生有对象则请求该女生的对象能否换一个女朋友把该女生分配给男生。如果无法做到返回 false对于每个男生而言每次访问女生都要设置一个 bool st[N] 数组防止递归时其他男生重复访问该女生。for(int i1;in1;i){ memset(st,false,sizeof st); if(find(i)) cnt; } bool find(int x){ for(int ih[x];i!-1;ine[i]){ int je[i]; if(!st[j]){ st[j]true; if(match[j]0||find(match[j])) { match[j]x; return true; } } } return false; }第四章数学知识1.质数1 判定一个数是否未质数使用试除法。思路如果 d | x那么 x / d| n因此只需要判断从 2 到 根号n 的数是否满足条件 i * i 可能会溢出使用 i n/i 枚举。bool div(int x){ if(x2) return false; for(int i2;ix/i;i){ if(x%i0) return false; } return true; }2 判断一个区间中的质数使用线性筛思路从2开始对于每个质数而言删去它的倍数留下的数就是所有质数o(nlonglongn)#include iostream using namespace std; const int N1e610; int prime[N]; bool st[N]; int main(void){ int n;cinn; int cnt0; for(int i2;in;i){ if(!st[i]){ prime[cnt]i; for(int j2;i*jn;j){ st[i*j]true; } } } coutcnt; return 0; }2. 约数1 对于一个数 N它的任意一个约数都可以表示为 d。约数个数约数之和p 和可以采用哈希的方式去存unordered_mapint,int q; while(n--){ int a;cina; int ta; for(int i2;ia/i;i){ while(t%i0){ tt/i; q[i]; } } if(t!1) q[t]; }2 最大公约数int gcd(int a,int b){ return b?gcd(b,a%b):a; }