0.倍增法1. 快速幂 洛谷P1226#includebits/stdc.h using namespace std; long long a,b,p; int main(){ cinabp; long long s 1,v a,t b; while(b){ if(b1) s s*v %p; b 1; v v*v %p; } printf(%lld^%lld mod %lld%lld,a,t,p,s); return 0; }1.前缀和与差分数组1. 一维数组求前缀和 acwing795#include bits/stdc.h using namespace std; // 1.一维数组求前缀和 acwing 795. 前缀和 const int N 1e510; int a[N],s[N]; int n,m,l,r; int main(){ cinnm; for(int i 1;in;i){ scanf(%d,a[i]); s[i] s[i-1] a[i]; } while(m--){ scanf(%d%d,l,r); printf(%d\n,s[r] - s[l-1]); } return 0; }2.二维数组求矩阵和 acwing796#include bits/stdc.h using namespace std; // 1.二维数组求前缀和 acwing 796. 子矩阵的和 int q[1010][1010],s[1010][1010]; int main(){ int n,m,k,x1,x2,y1,y2; cinnmk; for(int i 1;in;i){ for(int j 1;jm;j){ scanf(%d,q[i][j]); s[i][j] s[i][j-1]s[i-1][j]-s[i-1][j-1]q[i][j]; } } while(k--){ scanf(%d%d%d%d,x1,y1,x2,y2); printf(%d\n,s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]s[x1-1][y1-1]); } return 0; }3.一维数组差分 acwing797#include bits/stdc.h using namespace std; const int N 1e510; int n,m; int s[N],a[N]; void insert(int l,int r,int c){ a[l] c; a[r1] - c; } int main(){ // 不需要单独初始化差分数组 假设前缀和数组初始是 000000对应差分数组也是000000 // 现有前缀和数组s[n]是对其[1,1]加了a1,[2,2]加了a2,[3,3]加入a3 ...而成 cinnm; // 1.构建差分数组 对数组区间加一个数使用差分数组可以实现o(1)操作 for(int i 1,t;in;i){ scanf(%d,t); insert(i,i,t); } // 2.对差分数组进行修改 while(m--){ int l,r,c; scanf(%d%d%d,l,r,c); insert(l,r,c); } // 3.构建前缀和数组 for(int i 1;in;i){ s[i] s[i-1]a[i]; printf(%d ,s[i]); } return 0; }4.二维数组差分 acwing798#include bits/stdc.h using namespace std; int n,m,q; int a[1010][1010],s[1010][1010]; void insert(int x1,int y1,int x2,int y2,int c){ a[x1][y1] c; a[x1][y21] - c; a[x21][y1] - c; a[x21][y21] c; } int main(){ cinnmq; for(int i 1,t;in;i){ for(int j 1;jm;j){ scanf(%d,t); insert(i,j,i,j,t); } } while(q--){ int x1,x2,y1,y2,c; scanf(%d%d%d%d%d,x1,y1,x2,y2,c); insert(x1,y1,x2,y2,c); } for(int i 1;in;i){ for(int j 1;jm;j){ s[i][j] s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j]; printf(%d ,s[i][j]); } printf(\n); } }2.质数1.1 试除法#include bits/stdc.h using namespace std; //1.试除法 bool isprime(int n){ if(n2) return false; else{ for(int i 2;isqrt(n);i){ if(n%i 0) return false; } return true; } } int main(){ int n; cinn; for(int i 2;in;i) if(isprime(i)) couti ; return 0; }1.2 分解质因数 acwing867#include bits/stdc.h using namespace std; // 整数唯一分解定理 任何大于1的正整数都能表现成质数乘积的形式 // 试除法分解质因数 int t,n; int main(){ cint; while(t--){ cinn; for(int i 2;in/i;i){ int c 0; while(n%i0){ c; n/i; } if(c) couti cendl; if(n1) break; } if(n1) coutn 1endl; coutendl; } return 0; }2.埃式筛#include bits/stdc.h using namespace std; //2.埃式筛 //核心思想质数的倍数是合数 //时间复杂度O(nloglogn) //优点代码实现简单内存占用较小 //缺陷部分合数被多次标记如12会被2×6和3×4重复筛选 //适用场景对时间复杂度要求不高的中小规模数据筛选。 vectorint q(10010,1); int n; void prime(){ for(int i 2;isqrt(n);i){ if(q[i]){ for(int j i*i;jn;ji) q[j] 0; } } } int main(){ cinn; prime(); for(int i 2;in;i) if(q[i]) couti ; return 0; }3.欧拉筛#include bits/stdc.h using namespace std; //线性筛欧拉筛 //核心思想唯一分解定理强制每个合数仅被其最小质因数筛除 //时间复杂度O(n) //实现方式遍历时记录已发现素数并用当前数与已有素数依次相乘标记合数当遇到整除时终止内层循环。 //优点无重复计算适合大规模素数筛选 //代价需额外维护素数数组空间复杂度略高 vectorint q(10010,1); vectorint p; int n; void prime(){ for(int i 2;in;i){ if(q[i]) p.push_back(i); for(int j 0;jp.size()p[j]*in;j){ q[i*p[j]] 0; //当i整除p[j]质数时当前i*p[j]的最小质数是p[j]后续的数有更小的质数 if(i%p[j] 0) break; //不需要重复筛 如 4通过目前质数 2、3 -》4*2 8 2*2*2 -》4*3 123*42*2*3 } } } int main(){ cinn; prime(); for(int i 2;in;i) if(q[i]) couti ; for(int i 0;ip.size();i) coutp[i] ; return 0; }3.二分查找1.整数二分 acwing 789. 数的范围#include bits/stdc.h using namespace std; const int N 1e510; int q[N],n,m; int main() { cinnm; for(int i 0;in;i){ scanf(%d,q[i]); } int v; while(m--){ scanf(%d,v); int l 0,r n-1,mid; while(lr){ mid (lr)/2; if(q[mid] v) r mid; else l mid1; } if(q[l] ! v) cout-1 -1endl; else{ coutl; int l 0,r n-1,mid; while(lr){ mid (lr1)/2; if(q[mid] v) l mid; else r mid-1; } cout lendl; } } return 0; }2.二分答案 P1873 砍树#include bits/stdc.h using namespace std; const int N 1e610; int n,m; int q[N]; bool check(int x){ // 找到的高度应该满足切除后收集的木材和m long long sum 0; for(int i 0;in;i) if(q[i]x) sum q[i]-x; return summ; } int main(){ cinnm; for(int i 0;in;i){ scanf(%d,q[i]); } int l 0,r 4*1e5; while(lr){ int mid (lr1)/2; if(check(mid)) l mid; else r mid-1; } coutl; return 0; }3.实数二分 acwing790. 数的三次方根#include bits/stdc.h using namespace std; double n; bool check(double x){ return x*x*x n; } int main(){ cinn; // x*x*x n double l -10000,r 10000,eps 1e-8;//eps 误差一般比保留小数多2 while(r-l1e-8){ double mid (lr)/2; if(check(mid)) r mid; else l mid; } coutsetprecision(6)fixedl; return 0; }4.排序1.选择、冒泡、插入排序//时间复杂度最好O(n^2),一般O(n^2) //稳定性不稳定 void select_sort(int *q){ for(int i 0;in-1;i){ int mini i; for(int j i;jn;j){ if(q[j] q[mini]) mini j; } swap(q[i],q[mini]); } } //时间复杂度最好O(n),一般O(n^2) //稳定性稳定 void buble_sort(int *q){ //冒泡排序 for(int i 0;in-1;i){ int flag 1; for(int j 0;jn-1-i;j){ if(q[j]q[j1]) swap(q[j],q[j1]),flag 0; } if(flag 1) return; } } //时间复杂度最好O(n),一般O(n^2) //稳定性稳定 void insert_sort(int *q){ for(int i 1;in;i){ int temp q[i]; int j i-1; while(temp q[j] j0){ q[j1] q[j]; j --; } q[j1] temp; } }2.快速排序、归并排序#include iostream #include bits/stdc.h using namespace std; int q[100010],t[100010]; // 快速排序 【快速plus版】 void quick_sort(int* q,int l ,int r){ if(l r) return; int i l-1, j r1,x q[(lr)/2]; while(ij){ // 当ij时候结束循环 do i;while(q[i]x); do j--;while(q[j]x); if(ij) swap(q[i],q[j]); } //循环完一次后,ji 相差0或1 quick_sort(q,l,j); quick_sort(q,j1,r); } // 快速排序 【填坑版】-- 如果数据逆序时间复杂度 O(n^2) void quick_sort2(int *q,int l,int r){ if(lr) return; int i l,j r,x q[l];//1.将i位置的数挖出来 while(ij){ //2.1 j往左找到一个 x 的数填入i中 while(ij q[j] x) j--; if(ij) q[i] q[j]; //2.2 i往右找到一个 x 的数填入j中 while(ij q[i] x) i; if(ij) q[j--] q[i]; } //3.将原i中的数填入坑中 q[i] x; //4.递归下去处理其他区间 quick_sort(q,l,i-1); quick_sort(q,i1,r); } // 归并排序 void merge_sort(int *q,int l,int r){ if(lr) return; int mid (lr)/2; merge_sort(q,l,mid); merge_sort(q,mid1,r); int i l,j mid1,k l; while(imid jr) { if(q[i] q[j]) t[k] q[i]; else t[k] q[j]; } while(imid) t[k] q[i]; while(jr) t[k] q[j]; for(int c l;cr;c) q[c] t[c]; } int main(){ int n; cinn; for(int i 0;in;i) scanf(%d,q[i]); quick_sort(q,0,n-1); for(int i 0;in;i) coutq[i] ; }5.搜索算法1.一维排列数dfs n个选m进行排列区分位置#include bits/stdc.h using namespace std; int a[10],book[10],b[10]; // 图、标记、走了哪些 int n,m; void dfs(int step){ // 路线的深度 if(step m1) { for(int i 1;im;i) coutsetw(5)b[i]; coutendl; } for(int i 1;in;i){ // 路线的宽度 if(book[i] 0){ book[i] 1; b[step] a[i]; dfs(step1); book[i] 0; } } } int main(){ cinnm; //在n个数字中选m个进行排列区分位置 for(int i 1;i10;i) a[i] i; dfs(1); return 0; }2.一维组合数dfs n个选m进行组合不区分位置P1157 组合的输出#include bits/stdc.h using namespace std; int a[21],book[21],b[21]; // 总元素、标记是否选用、存储已选用元素 int n,r; void dfs(int step,int newi){ //当前选到了第几个数、当前从第几个数开始选 if(step r1){ // 递归深度控制【组合的个数】 for(int i 1;ir;i) coutsetw(3)b[i]; coutendl; } for(int i newi;in;i){ // 递归宽度控制一次选择的元素个数 if(book[i] 0 ){ book[i] 1; b[step] a[i]; dfs(step1,i1); book[i] 0; } } } int main(){ cinnr; for(int i 1;in;i){ a[i] i; } dfs(1,1); return 0; }3.一维组合排列dfs P1219 八皇后#include bits/stdc.h using namespace std; int a[14],b[14]; int mvis[14],lvis[28],rvis[28]; // 标记 当前列、左对角线、右对角线上有没有棋子 int n,c; void dfs(int step){ if(step n1){ c; if(c3){ for(int i 1;in;i) coutb[i] ; coutendl; } return; } for(int i 1;in;i){ if(mvis[i] 0 lvis[istep]0 rvis[i-stepn] 0){ mvis[i] 1,lvis[istep] 1,rvis[i-stepn] 1; b[step] a[i]; dfs(step1); mvis[i] 0,lvis[istep] 0,rvis[i-stepn] 0; } } } int main(){ cinn; for(int i 1;i14;i) a[i] i; dfs(1); coutc; return 0; }4.二维迷宫dfs P1605#include bits/stdc.h using namespace std; // 1.准备好存储容器: 原地图、路径地图 int a[10][10],vis[10][10]; int nt[4][2] {{1,0},{0,1},{0,-1},{-1,0}}; int sum,n,m,t; int sx,sy,fx,fy; void dfs(int x,int y){ //4.到达终点 if(x fx y fy){ sum; return; } //3.开始移动:注意索引范围、有无标记、障碍物 for(int i 0;i4;i){ int xt xnt[i][0]; int yt ynt[i][1]; if(xt1 || xtn||yt1||ytm) continue; if(vis[xt][yt] 0a[xt][yt]0){ vis[xt][yt] 1; dfs(xt,yt); //解路径总数 - 需要回溯 vis[xt][yt] 0; } } } int main(){ cinnmt; cinsxsyfxfy; //2.初始化地图障碍物、标记 while(t--){ int x,y; cinxy; a[x][y] 1; } vis[sx][sy] 1; dfs(sx,sy); coutsum; return 0; }5.二维迷宫bfs 最短路【一本通】1252走迷宫#include bits/stdc.h using namespace std; // 1.准备工作数据存储 int n,m; char a[41][41],vis[41][41]; // 地图、路径标记图 int nt[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组 struct Node{ int x,y,s; // 当前处于x,y点s已走的步数 }head; int bfs(int x,int y){ // 2.初始化标记路径、队列 vis[x][y] 1; queueNode que; que.push(Node({x,y,1})); // 3.搜索遍历 入队、出队 while(!que.empty()){ head que.front();//存储队头 que.pop();//出队 for(int i 0;i4;i){ int xt head.xnt[i][0]; int yt head.ynt[i][1]; if(xt1||xtn||yt1||ytm) continue; if(vis[xt][yt] 0 a[xt][yt] .){ vis[xt][yt] 1; //入队 que.push(Node({xt,yt,head.s1})); //判断终点 if(xtn ytm) return que.back().s; } } } } int main() { cinnm; for(int i 1;in;i){ for(int j 1;jm;j){ cina[i][j]; } } coutbfs(1,1); return 0; }6.泛洪算法 【一本通】1249Lake Counting#includebits/stdc.h using namespace std; int n,m,s; char a[200][200]; int nt[8][2] {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}}; struct node{ int x,y; }; // 1.容器准备 标记数组、原地图、队列、方向数组 void bfs(int x,int y){ // 2.队列、标记数组初始化 queuenode q; q.push({x,y}); a[x][y] .; // 3.队列方向数组组合 while(!q.empty()){ node head q.front(); q.pop(); for(int i 0;i8;i){ int xt head.xnt[i][0]; int yt head.ynt[i][1]; if(xt1||yt1||xtn||ytm||a[xt][yt].) continue; a[xt][yt] .; q.push({xt,yt}); } } } int main(){ cinnm; for(int i 1;in;i){ for(int j 1;jm;j){ cina[i][j]; } } //1.找未被标记的坑 for(int i 1;in;i){ for(int j 1;jm;j){ if(a[i][j] W){ bfs(i,j); s ; } } } couts; return 0; }6.动态规划1.硬币问题 B3635#includebits/stdc.h using namespace std; const int N 1E610; int dp[N]; int n; int main(){ cinn; for(int i 1;in;i){ dp[i] dp[i-1]1; if(i-50) dp[i] min(dp[i],dp[i-5]1); if(i-110) dp[i] min(dp[i],dp[i-11]1); } coutdp[n]; return 0; }2.最长上升子序列 AcWing 895#include bits/stdc.h using namespace std; int n; int q[1010]; int dp[1010]; int main(){ cinn; for(int i 1;in;i){ cinq[i]; //1.找前面比自己小的如果小最大的dp[j] int maxv 0; for(int j 1;jn;j){ if(q[i]q[j]dp[j]maxv) { maxv dp[j]; } } //2.如果找到了就和前面最大的dp[j]结合没有就自身为1个序列 if(maxv) dp[i] maxv 1; else dp[i] 1; } cout*max_element(dp1,dpn1); return 0; }3.LCS最长公共子序列 AcWing 897#include bits/stdc.h using namespace std; string a,b; int dp[1010][1010]; int main(){ cinab; a a; b b; for(int i 1;ia.size();i){ for(int j 1;jb.size();j){ if(a[i] b[j]) dp[i][j] dp[i-1][j-1] 1; else dp[i][j] max(dp[i-1][j],dp[i][j-1]); } } coutdp[a.size()-1][b.size()-1]; return 0; }4. 01背包问题 【一本通】1267#include bits/stdc.h using namespace std; int dp[51][210]; // 第前i个物品下的第j容量时最大的总价值 int w[51],v[51]; int main() { int m,n; cinmn; for(int i 1;in;i) cinw[i]v[i]; for(int i 1;in;i){ for(int j 1;jm;j){ //1.如果j容量下第i个物品下拿不了dp[i-1][j] if(w[i]j) dp[i][j] dp[i-1][j]; //2.如果能拿 else{ //2.(1) 不拿 dp[i-1][j] //2.(2) 拿 v[i] dp[i-1][j-w[i]] dp[i][j] max(dp[i-1][j],v[i] dp[i-1][j-w[i]]); } } } coutdp[n][m]; }5.完全背包问题 【一本通】1267#includebits/stdc.h using namespace std; int m,n; int w[210],c[210]; int dp[40][210]; int main(){ cinmn; for(int i 1;in;i){ cinw[i]c[i]; } for(int i 1;in;i){ for(int j 1;jm;j){ // 两种选择 // 1.不拿无条件可选择项 dp[i][j] dp[i-1][j]; // 2.再拿一次 (该物品可重复拿) if(j-w[i]0) dp[i][j] max(dp[i][j],dp[i][j-w[i]]c[i]); } } coutmaxdp[n][m]; return 0; }7.链表1.单向链表#includebits/stdc.h using namespace std; struct node{ int data; node* next; node(int v):data(v),next(NULL) { //初始化结构体 } } *head; int main(){ // 1.创建链表 // a.单个添加 node* a new node(10); node* b new node(20); node* c new node(30); head a; a-next b; b-next c; // b.批量添加 for(int i 1,t;i5;i){ cint; node* p new node(t); p-next head; head p; } //2.遍历链表 for(node* i head;i;i i-next){ couti-data ; } //3.插入值 node* p new node(40); // a.插入头部 // 与批量创建相同 // b.中间插入 如在10后面插入 for(node* i head;i;i i-next){ if(i-data 10){ p-next i-next; i-next p; } } //4.删除某结点 // a.删除头结点 head head-next; // b.删除某值v int v; cinv; node* t new node(0); t-next head; //创建一个空节点方便删除头结点 for(node* i t;i-next;i i-next){ //判断下一个节点是否存在 if(i-next-data v){ if(i-next head) head i-next-next; //如果删除头结点先指向下一位 i-next i-next-next; } } return 0; }2.双向链表#includebits/stdc.h using namespace std; // 双向链表 struct node{ int data; node* next; node* prv; node(int v):data(v),next(NULL),prv(NULL) { //初始化结构体 } } *head; int main(){ return 0; }3.循环链表#includebits/stdc.h using namespace std; // 循环链表 struct node{ int data; node* next; node(int v):data(v),next(NULL) { //初始化结构体 } } *head; int main(){ // 1.创建链表 node* a new node(10); node* b new node(20); node* c new node(30); head a; a-next b; b-next c; c-next head; return 0; }8.栈和队列1.栈STL#includebits/stdc.h using namespace std; // 栈 : 先进后出 FILO \ 后进先出LIFO stackint stk; int main(){ for(int i 0;i10;i){ stk.push(i); //入栈 } while(!stk.empty()){//判断是否为空 coutstk.top()endl; //获取栈头 stk.pop(); //出栈 } return 0; }2.栈数组模拟#include bits/stdc.h using namespace std; const int N 100010; int stk[N]; // 栈的存储数组对应队列的 q[N] int top; // 栈顶指针初始为0指向下一个可插入的空位 // 初始化栈 void init() { top 0; } // 入栈将元素 x 压入栈顶 void push(int x) { stk[top] x; } // 出栈弹出栈顶元素 void pop() { top--; } // 获取栈顶元素不弹出 int get_top() { return stk[top - 1]; } // 判断栈是否为空 bool empty() { return top 0; } // 获取栈中有效元素个数 int size() { return top; } // 清空栈 void clear() { top 0; } int main() { // 1. 初始化 init(); // 2. 入栈 int n, t; cin n; while (n--) { cin t; push(t); } // 3. 栈的遍历从栈顶到栈底依次弹出 while (!empty()) { cout get_top() ; pop(); } return 0; }3.队列STL#includebits/stdc.h using namespace std; // 队列 : 先进先出 FIFO \ 后进后出LILO queueint que; int main(){ for(int i 0;i10;i){ que.push(i); //入队 } while(!que.empty()){ //判断是否为空 coutque.front()endl; //查看队头 que.pop(); //出队 } return 0; }4.队列数组模拟#include bits/stdc.h using namespace std; const int N 100010; int q[N]; int head, tail; // head队头tail队尾初始都是0 // 初始化 void init() { head 0; tail 0; } // 入队 void push(int x) { q[tail] x; } // 出队 void pop() { head; } // 获取队头元素 int front() { return q[head]; } // 获取队尾元素 int back() { return q[tail - 1]; } // 判断队列是否为空 bool empty() { return head tail; } // 获取队列有效元素个数 int size() { return tail - head; } // 清空队列 void clear() { head 0; tail 0; } int main() { //1.初始化 init(); //2.入队 int n,t; cinn; while(n--){ cint; push(t); } //3.队的遍历 while(!empty()){ coutfront() ; pop(); } return 0; }9.树1.树的顺序存储与遍历#include bits/stdc.h using namespace std; int n, a[110]; void first(int i){ // 前序遍历 根结点root、左子树、右子树 if(in) return; couta[i] ; first(2*i); first(2*i1); } void mid(int i){ // 中序遍历 左子树 、根结点root、右子树 if(in) return; mid(2*i); couta[i] ; mid(2*i1); } void last(int i){ // 后序遍历 左子树 、右子树 、根结点root if(in) return; last(2*i); last(2*i1); couta[i] ; } int main() { cinn; for(int i 1;in;i) cina[i]; first(1); coutendl; mid(1); coutendl; last(1); } //7 //4 2 6 1 3 5 710.图1.邻接矩阵的存储#include bits/stdc.h using namespace std; int g[110][110]; int n,m,a,x,y; int main(){ cinnm; while(m--){ cinaxy; g[x][y] 1; if(a 1) g[y][x] 1; } for(int i 0;in;i){ for(int j 0;jn;j){ coutg[i][j] ; } coutendl; } //4 4 //0 0 1 //1 0 2 //0 3 1 //1 2 32.邻接表的存储#includebits/stdc.h using namespace std; int n,m; vectorint g[110]; int main(){ cinnm; while(m--){ int a,x,y; cinaxy; g[x].push_back(y); if(a1) g[y].push_back(x); } for(int i 0;in;i){ couti:; for(int j g[i].size()-1;j0;j--){ coutg[i][j] ; } coutendl; } //4 4 //0 0 1 //1 0 2 //0 3 1 //1 2 3 return 0; }