文章目录前言第一讲 基础算法快速排序归并排序*AcWing 788. 逆序对的数量二分高精度前缀和与差分AcWing 796. 子矩阵的和*AcWing 797. 差分双指针算法位运算离散化区间合并*AcWing 803. 区间合并第二讲 数据结构单链表双链表栈队列单调栈*AcWing 830. 单调栈单调队列*AcWing 154. 滑动窗口(单调队列)KMP(暴力算就行)Trie*AcWing 835. Trie字符串统计(map哈希表应用)并查集*AcWing 837. 连通块中点的数量堆*AcWing 839. 模拟堆(集合模拟堆)哈希表*AcWing 841. 字符串哈希（s.substr(pos, len)比较不同位置子串相等）第三讲 搜索与图论DFS*AcWing 842. 排列数字(全排列n!)BFS*AcWing 844. 走迷宫(数组的二维bfs最短路径)树与图的深度优先遍历AcWing 846. 树的重心(图树双向边一维dfs最短路径)树与图的广度优先遍历*AcWing 847. 图中点的层次(图树有向边一维bfs最短路径)拓扑排序Dijkstrabellman-fordspfaFloydPrimKruskal染色法判定二分图匈牙利算法第四讲 数学知识质数AcWing 866. 试除法判定质数*AcWing 867. 分解质因数*AcWing 868. 筛质数(诶氏筛法)约数*AcWing 869. 试除法求约数(if(x%i == 0),[i,x/i]因子成对出现)AcWing 870. 约数个数*AcWing 872. 最大公约数欧拉函数快速幂扩展欧几里得算法中国剩余定理高斯消元容斥原理博弈论第五讲 动态规划背包问题AcWing 2. 01背包问题 （**1组物品，每个物品只能用一次**）AcWing 3. 完全背包问题 （**1组物品，每个物品可用无限次**）AcWing 4. 多重背包问题 （**1组物品，每个物品最多用k次**）AcWing 9. 分组背包问题 （**n组物品，每组物品只能选一次**）线性DPAcWing 898. 数字三角形AcWing 895. 最长上升子序列 （**子序列可以是不连续的子序列**）AcWing 897. 最长公共子序列 （**A、B两串的最长公共子串c**）AcWing 902. 最短编辑距离(A串变B串需要步骤)区间DPAcWing 282. 石子合并计数类DPAcWing 900. 整数划分数位统计DP状态压缩DP树形DP记忆化搜索AcWing 901. 滑雪第六讲 贪心区间问题AcWing 905. 区间选点 （**每个集合右端点排序**）AcWing 908. 最大不相交区间数量 （每个集合右端点排序，题解同上题）AcWing 906. 区间分组 （每个集合左端点排序）Huffman树AcWing 148. 合并果子 (小堆实现哈夫曼权值)排序不等式AcWing 913. 排队打水 (小堆实现long long res += a * s.size())绝对值不等式AcWing 104. 货仓选址(升序取中点res += | a[i] - a[n/2] |)推公式AcWing 125. 耍杂技的牛(S[i]+W[i]越大放越下面)前言基础知识：C++ 标准库 菜鸟教程系统学习：AcWing算法基础课算题计划：图解算法数据结构【1】AcWing_Plan 一轮：2024.3.12 - 2024.4.26【2】LeetCode_Plan 算法刷题攻略|| 二轮：2024.5.1 – 2024.5.18【3】通关要求：简单/经典/模板题有手就行, 偏题难题选择记忆算法 :搜索、查找、排序、双指针、回溯、分治、动态规划、贪心、位运算数据结构 :数组、栈、队列、字符串、链表、树、图、堆、哈希表等。第一讲 基础算法包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容快速排序AcWing 785. 快速排序//【思路】首尾ij双指针+递归左右排序 #includeiostream using namespace std; //指明命名空间，才能使用cout和endl等C++中的标识符 const int N = 100010;//定义常量，类比C语言的#define int N = 100000; int q[N]; void quick_sort(int q[],int L,int R) { //递归终止条件 if(L = R) return; int i = L-1, j = R+1, x = q[(L+R)1];//初始化变量 //递归执行条件 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_sort(q,j+1,R); } int main() { int n ; scanf("%d",n); for(int i=0; in; i++) scanf("%d",q[i]); quick_sort(q,0,n-1); for(int i=0; in; i++) printf("%d ",q[i]);//"%d "注意题干要求输出格式空格开 return 0; }AcWing 786. 第k个数#includeiostream using namespace std; const int N = 100010; int q[N]; void quick_sort(int q[],int L,int R) { //递归终止条件 if(L = R) return; int i = L-1, j = R+1, x = q[(L+R)1];//初始化变量 //递归执行条件 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_sort(q,j+1,R); } int main() { int n ,k; scanf("%d%d",n,k); for(int i=0; in; i++) scanf("%d",q[i]); quick_sort(q,0,n-1); cout q[k-1] endl;//等价于printf("%d",q[k-1]); return 0; }归并排序AcWing 787. 归并排序//【1】sort大法调用功能库函数 #includeiostream #includealgorithm using namespace std; const int N=100010; int q[N]; int main(){ int n; cin n; for(int i=0;in;i++) cin q[i]; sort(q,q+n); for(int i=0;in;i++) cout q[i] " "; return 0; }#includebits/stdc++.h using namespace std; const int N = 100010; int q[N],tmp[N];//辅助数组tmp void merge_sort(int q[],int l,int r){ //递归终止条件 if(l = r) return; int mid = (l+r) 1; //递归入口 merge_sort(q,l,mid); merge_sort(q,mid+1,r); //递归执行条件 int k=0, i=l, j=mid+1; while(i=mid j=r){ if(q[i] = q[j]) tmp[k++] = q[i++]; else{ tmp[k++] = q[j++]; } } //A指针未到尾部，B指针便利完B数组，A剩余元素直接加到B尾部 while(i=mid) tmp[k++] = q[i++]; while(j=r) tmp[k++] = q[j++]; //递归结果数组复制 for(int i=l,j=0 ; i=r ;i++,j++) q[i] = tmp[j]; } int main(){ int n; cin n; for(int i=0;in;i++) cin q[i]; merge_sort(q,0,n-1); for(int i=0;in;i++) cout q[i] " " ; return 0; }*AcWing 788. 逆序对的数量#includebits/stdc++.h using namespace std; const int N = 100010; int q[N],tmp[N];//辅助数组tmp long long res = 0; void merge_sort(int q[],int l,int r){ //递归终止条件 if(l = r) return; int mid = (l+r) 1; //递归入口 merge_sort(q,l,mid); merge_sort(q,mid+1,r); //递归执行条件 int k=0, i=l, j=mid+1; while(i=mid j=r){ //分治思想 if(q[i] = q[j]) tmp[k++] = q[i++]; else{ tmp[k++] = q[j++]; res += mid-i+1;//当ij且q[i]q[j]符合题意，满足数量为mid-i+1 } } //A指针未到尾部，B指针便利完B数组，A剩余元素直接加到B尾部 while(i=mid) tmp[k++] = q[i++]; while(j=r) tmp[k++] = q[j++]; //递归结果数组复制 for(int i=l,j=0 ; i=r ;i++,j++) q[i] = tmp[j]; } int main(){ int n; cin n; for(int i=0;in;i++) cin q[i]; merge_sort(q,0,n-1); cout res endl ; return 0; }法2：冒泡排序暴力(会超时)#include bits/stdc++.h using namespace std; const int N = 1e5+10; int q[N]; int main(){ int n ; cin n; for (int i = 0 ; i n ; i ++) cin q[i]; int res = 0; for (int i = 0; i n ; i++) for(int j = i+1; j n ; j ++) if(q[i] q[j]) res++; cout res endl; return 0; }二分AcWing 789. 数的范围#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N]; int main(){ int n,q; cin n q; for(int i=0;in;i++) cin a[i]; while(q--){ int k; cin k; int x1,x2; //eg. a[1,2,2,3,3,4]、K=3、【x1=3 , x2=5-1=4】= res = [3,4] // K=5、【x1=5 , x2=5-1=4】= res = [-1,-1] x1 = lower_bound(a, a + n, k) - a;//找第一个=k的位置,找不到返回end x2 = upper_bound(a, a + n, k) - a - 1;//找第一个k的位置 if(x1 == x2+1) printf("-1 -1\n"); else printf("%d %d\n",x1,x2); } return 0; }法2；常规二分法#includeiostream using namespace std; int a[100010]; int n,q; int main(){ scanf("%d%d",n,q); for(int i=0;in;i++) scanf("%d",a[i]); while(q--) { int k; scanf("%d",k); //找k出现的起始位置 int l=0,r=n-1; while(lr){ int mid=l+r1; if(a[mid]=k) r=mid; else l=mid+1; } //没找到 if(a[l]!=k) printf("-1 -1\n"); //找k出现的的终止位置 else { printf("%d ",l); int l=0,r=n-1; while(lr){ int mid=l+r+11; if(a[mid]=k) l=mid; else r=mid-1; } printf("%d\n",l); } } return 0; }AcWing 790. 数的三次方根法1；调用cbrt()开立方根函数 //cbrt(-27.00) = -3.00#includebits/stdc++.h using namespace std; int main(){ double n; cin n; printf("%.6lf\n",cbrt(n)); return 0; }法2；常规二分法#include iostream using namespace std; int main() { double x; cin x; double l = -100, r = 100; while (r - l 1e-8) { double mid = (l + r) / 2; if (mid * mid * mid = x) r = mid; else l = mid; } printf("%.6lf\n", l); return 0; }高精度AcWing 791. 高精度加法#includebits/stdc++.h using namespace std; const int N = 110; int a[N],b[N],c[N]; int main(){ string s1,s2; cin s1 s2; //reverse（）函数用来翻转数组，字符串，向量； reverse(s1.begin(),s1.end()); //reverse(s1.begin(),s1.end()); 翻转整个字符串 reverse(s2.begin(),s2.end()); //reverse(s.begin()+i,s.begin()+k); 翻转下标i到k（不包含k） for(int i = 0;i s1.size();i++) a[i] = s1[i] - 48; for(int i = 0;i s2.size();i++) b[i] = s2[i] - 48; int len = max(s1.size(), s2.size()); int jinwei = 0; for(int i = 0;i len;i++){ c[i] = a[i] + b[i] + jinwei; jinwei = c[i] / 10; c[i] = c[i] % 10; } if(jinwei == 1) cout "1"; for(int i = len - 1;i = 0;i--) cout c[i]; return 0; }AcWing 792. 高精度减法#includeiostream using namespace std; int a[100010],lena,b[100010],lenb,c[100010],lenc; string A,B; void div(int a[],int b[]){ lenc=max(lena,lenb); for(int i=0;ilenc;i++){#includeiostream using namespace std; int a[100010],lena,b[100010],lenb,c[100010],lenc; string A,B; void div(int a[],int b[]){ lenc=max(lena,lenb); for(int i=0;ilenc;i++){ c[i]+=a[i]-b[i]; if(c[i]0){ c[i+1]--; c[i]+=10; } } while(!c[lenc-1]lenc1) lenc--; } bool bigger(){ if(lenalenb) return true; if(lenblena) return false; for(int i=lena-1;i=0;i--) if(a[i]b[i]) return true; else if(b[i]a[i]) return false; return true; } int main(){ cinAB; lena = A.size(),lenb = B.size(); for(int i=0;ilena;i++) a[i]=A[lena-1-i]-'0'; for(int i=0;ilenb;i++) b[i]=B[lenb-1-i]-'0'; if(bigger()) div(a,b); else{printf("%c",'-'); div(b,a);} for(int i=lenc-1;i=0;i--) printf("%d",c[i]); } c[i]+=a[i]-b[i]; if(c[i]0){ c[i+1]--; c[i]+=10; } } while(!c[lenc-1]lenc1) lenc--; } bool bigger(){ if(lenalenb) return true; if(lenblena) return false; for(int i=lena-1;i=0;i--) if(a[i]b[i]) return true; else if(b[i]a[i]) return false; return true; } int main(){ cinAB; lena=A.size(),lenb=B.size(); for(int i=0;ilena;i++) a[i]=A[lena-1-i]-'0'; for(int i=0;ilenb;i++) b[i]=B[lenb-1-i]-'0'; if(bigger()) div(a,b); else{printf("%c",'-'); div(b,a);} for(int i=lenc-1;i=0;i--) printf("%d",c[i]); }AcWing 793. 高精度乘法#include bits/stdc++.h using namespace std; vectorint mul(vectorint A, int b) { vectorint C; int t = 0; for (int i = 0; i A.size() || t; i ++ ){ if (i A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() 1 C.back() == 0) C.pop_back(); return C; } int main(){ string a; int b; cin a b; vectorint A; for (int i = a.size()-1; i = 0; i--) A.push_back(a[i] - '0'); auto C = mul(A, b); for (int i = C.size()-1; i = 0; i--) printf("%d", C[i]); return 0; }AcWing 794. 高精度除法#include bits/stdc++.h using namespace std; vectorint div(vectorint A, int b, int r) { vectorint C; r = 0; for (int i = A.size() - 1; i = 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() 1 C.back() == 0) C.pop_back(); return C; } int main() { string a; vectorint A; int B; cin a B; for (int i = a.size()-1; i = 0; i--) A.push_back(a[i] - '0'); int r; auto C = div(A, B, r); for (int i = C.size()-1; i = 0; i--) cout C[i]; cout endl r endl; return 0; }前缀和与差分AcWing 795. 前缀和#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N],s[N]; int main(){ int n,m; cin n m; for(int i=1;i=n;i++) cin a[i]; for(int i=1;i=n;i++) s[i] = s[i-1] + a[i];//前缀和初始化 while(m--){ int l,r; cin l r; cout s[r]-s[l-1] endl;//区间和计算 } return 0; }AcWing 796. 子矩阵的和#includebits/stdc++.h using namespace std; const int N = 1010; int s[N][N]; int main(){ int n,m,q; cin n m q; for(int i=1;i=n;i++) for(int j=1;j=m;j++){ cin s[i][j]; s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];//二维矩阵初始化 } while(q--){ int x1,y1,x2,y2; scanf("%d%d%d%d",x1,y1,x2,y2); //二维前缀和 printf("%d\n",s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]); } return 0; }*AcWing 797. 差分问题：给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c , a[r] + c;写法一：#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N],b[N]; int main(){ int n,m; cin n m; for(int i=1;i=n;i++){ cin a[i]; b[i] = a[i] - a[i-1];//初始化差分数组,默认a[0]=0 } while(m--){ int l,r,c; cin l r c; b[l] += c; //将序列中[l, r]之间的每个数都加上c b[r+1] -= c; } for(int i=1;i=n;i++){ a[i] = a[i-1] + b[i];//前缀和运算 cout a[i] " " ; } return 0; }写法二：#includebits/stdc++.h using namespace std; const int N = 100010; int a[N],b[N]; void insert(int l,int r,int c){ b[l] += c; b[r+1] -= c; } int main(){ int n,m; cin n m; for(int i=1;i=n;i++){ cin a[i]; insert(i,i,a[i]);//初始化差分数组,默认a[0]=0 } while(m--){ int l,r,c; scanf("%d%d%d",l,r,c); insert(l,r,c);//将序列中[l, r]之间的每个数都加上c } for(int i=1;i=n;i++) { b[i] += b[i-1];//差分操作指定段数组 cout b[i] " "; } return 0; }AcWing 798. 差分矩阵#includebits/stdc++.h using namespace std; const int N = 1010; int a[N][N], b[N][N]; //差分插入操作 void insert(int x1, int y1, int x2, int y2, int c) {//对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main(){ int n, m, q; cin n m q; for (int i = 1; i = n; i ++) for (int j = 1; j = m; j ++){ cin a[i][j]; insert(i, j, i, j, a[i][j]);//初始化差分矩阵 } while (q -- ){ int x1, y1, x2, y2, c; scanf("%d%d%d%d%d",x1,y1,x2,y2,c); insert(x1, y1, x2, y2, c);//构建差分矩阵 } for (int i = 1; i = n; i ++){ for (int j = 1; j = m; j ++) { b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];//进行差分操作 cout b[i][j] " " ; //输出差分后的结果 } printf("\n");//换行输出 } return 0; }双指针算法AcWing 799. 最长连续不重复子序列#includebits/stdc++.h using namespace std; const int N=100010; int a[N],s[N]; //a存数据，b作为桶记录每个数字出现的次数 int main(){ int n; cin n; for(int i=0;in;i++) cin a[i]; int res=0; for(int i=0,j=0;in;i++) { s[a[i]]++; //指向一个数，对应数的出现次数+1 while(ji s[a[i]]1) { //s[a[i]]1,说明当前区间有重复元素a[i]. s[a[j]]--; //把j对应位置的数删掉, j指针向前走 j++; } res=max(res,i-j+1); //每轮取当前连续区间长度的max } cout res endl; return 0; }AcWing 800. 数组元素的目标和 给定两个升序排序的有序数组 A 和 B，以及一个目标值 x, 数组下标从 0开始。 请你求出满足 A[i]+B[j]=𝑥 的数对 (𝑖,𝑗) . 数据保证有唯一解。#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N],b[N]; int main(){ int n,m,x; cin n m x; for(int i=0; in; i++) cin a[i]; for(int i=0; im; i++) cin b[i]; //i-A[0]、j-B[m-1] ,j只能往左移 for(int i=0,j=m-1; in; i++) { while(j = 0 a[i]+b[j] x) j--; //a[i]+b[j]x, AB数组升序，只能j指针往左移 if(j = 0 a[i]+b[j] == x) printf("%d %d\n",i,j); //走到j i时, i指针往右移继续判断，题干可以确定有唯一值 } return 0; }AcWing 2816. 判断子序列#includebits/stdc++.h using namespace std; const int N = 100010; int a[N],b[N]; int main(){ int n,m; cin n m; for(int i=0;in;i++) cin a[i]; for(int i=0;im;i++) cin b[i]; int i = 0; for(int j = 0; j m; j++){//a[i]!=b[j],j右移一位继续匹配 if(i n a[i] == b[j]) i++; } if(i == n) puts("Yes"); //i=n跳出循环,找到b中子序列a else puts("No"); return 0; }位运算AcWing 801. 二进制中1的个数法1：STL库 bst.count()函数#includebits/stdc++.h using namespace std; int main(){ int n; cin n; int arr[n]; for(int i=0; in ;i++) cin arr[i]; for(int i=0; in ;i++){ bitset32 bst(arr[i]); //bitset32 bst(0xffff);定义bst数组共有32位,把bst中0~15低位置为1,剩余高位置0 cout bst.count() " "; } return 0; }法2：#include bits/stdc++.h using namespace std; //返回N的最后一位1 = n(-n) int lowbit(int x) {//正数x的反码为-x，补码为取反+1 return x (-x);//x -x == x (~x +1) } int main(){ int n; cin n; while (n -- ){ int x; cin x; int res = 0; while(x){ x -= lowbit(x);//每次减去x的最后一位1 res ++;//1个数更新 } cout res " "; } return 0; }离散化AcWing 802. 区间和法1：#include iostream #include vector #include algorithm using namespace std; const int N = 300010; //n次插入和m次查询相关数据量的上界 int n, m; int a[N];//存储坐标插入的值 int s[N];//存储数组a的前缀和 vectorint alls; //存储（所有与插入和查询有关的）坐标 vectorpairint, int add, query; //存储插入和询问操作的数据 int find(int x) { //返回的是输入的坐标的离散化下标 int l = 0, r = alls.size() - 1; while (l r) { int mid = l + r 1; if (alls[mid] = x) r = mid; else l = mid + 1; } return r + 1; } int main() { scanf("%d%d", n, m); for (int i = 1; i = n; i++) { int x, c; scanf("%d%d", x, c); add.push_back({x, c}); alls.push_back(x); } for (int i = 1; i = m; i++) { int l , r; scanf("%d%d", l, r); query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } //排序，去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); //执行前n次插入操作 for (auto item : add) { int x = find(item.first); a[x] += item.second; } //前缀和 for (int i = 1; i = alls.size(); i++) s[i] = s[i-1] + a[i]; //处理后m次询问操作 for (auto item : query) { int l = find(item.first); int r = find(item.second); printf("%d\n", s[r] - s[l-1]); } return 0; }法2：思路： 因为范围太大， 所以不能开一个大数组//开一个小数组 : 范围就是 add(index) + question(index) ， 两者的范围， 排序去重//我们在index + c, 就是要在新数组的新下标下标操作#includebits/stdc++.h using namespace std; const int N = 1000010; int a[N], s[N]; typedef pairint, int pii; int main(){ int n, m; cin n m; vectorpii add, query; vectorint all; for(int i = 0; i n; i++) { int l , r; cin l r; add.push_back({l, r}); //存储单独一个 all.push_back(l); } for(int i = 0; i m; i++) { int l , r; cin l r; all.push_back(l); all.push_back(r); query.push_back({l, r}); } // 去重 sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); //去重 //获取新下标 unordered_mapint, int get_index; for(int i = 1; i = all.size(); i++) get_index[all[i-1]] = i;//注意这里 all[i-1],不是i // 处理插入 for(int i = 0; i add.size(); i ++) { int old_index = add[i].first; int c = add[i].second; int new_index = get_index[old_index]; a[new_index] += c; } // 预处理前缀和 for(int i = 1; i = all.size(); i++) a[i] += a[i - 1]; // 处理询问 for(auto p : query) { int l = p.first, r = p.second; int l2 = get_index[l], r2 = get_index[r]; cout (a[r2] - a[l2 - 1]) endl; } return 0; }区间合并*AcWing 803. 区间合并法1:#includebits/stdc++.h using namespace std; const int N = 100100; int n,cnt;//cnt为初始满足条件的区间个数 pairint,int a[N]; //类似结构体A[N]={(1，2),(1，2)...} int main(){ //输入数据 cin n; for(int i=1; i=n; i++) cin a[i].first a[i].second; //每个集合左端点排序 sort(a+1,a+1+n); //依次遍历开始比较 cnt = n; for(int i=1; in ; i++){ //相邻两集合 有交集 或 为父子集 if(a[i].second = a[i+1].first){ cnt --; a[i+1].first = a[i].first; a[i+1].second = max(a[i+1].second, a[i].second); } //相邻两集合 无交集 else continue; } //输出结果 cout cnt endl; return 0; }✔法2：贪心模板#includebits/stdc++.h using namespace std; const int N=1e5+10; typedef pairint,int PII; PII a[N]; int main(){ int n; cinn; for(int i=0;in;i++) cin a[i].first a[i].second; sort(a,a+n);//每个集合左端点排序 int end = a[0].second, res = 1;//初始排好序的第1个集合算1个区间 for(int i=1;in;i++){ //相邻两集合 无交集 if(end a[i].first){ res++; end = a[i].second; } //相邻两集合 有交集 或 为父子集 else end = max(end, a[i].second); } cout res endl; return 0; }第二讲 数据结构包括单链表，双链表，栈，队列，单调栈，单调队列，KMP，Trie，并查集，堆，哈希表等内容单链表AcWing 826. 单链表#includebits/stdc++.h using namespace std; const int N = 1e5+10; int head,e[N],ne[N],idx; //head头节点下标, e[i]节点i的值, ne[i]节点i的next指针, idx存储当前指向的点 //初始化 void init(){ head = -1; idx = 0; } //头插操作 void add_to_head(int x){ e[idx] = x; ne[idx] = head; head = idx++; } //后插x操作 void add(int k,int x){ e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } // 删头结点，需要保证头结点存在 void remove_head(){ head = ne[head]; } //删除下标为k的下一个点 void remove(int k){ ne[k] = ne[ne[k]]; } int main(){ int m; cin m; init(); while(m--){ char op;int k,x; cin op; if(op == 'H'){//头插操作 cin x; add_to_head(x); } if(op == 'I'){//后插操作 cin k x; add(k-1,x);//第k个数，下标从0开始算 } if(op == 'D'){//后删操作 cin k; if(k == 0) remove_head();//删除头节点 else remove(k-1);//第k个数，下标从0开始算 } } for(int i=head; i != -1; i = ne[i]) cout e[i] " "; return 0; }双链表AcWing 827. 双链表#include bits/stdc++.h using namespace std; const int N = 100010; int m; int e[N], l[N], r[N], idx; // 在节点a的右边插入一个数x void insert(int a, int x){ e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = idx ++ ; } // 删除节点a void remove(int a){ l[r[a]] = l[a]; r[l[a]] = r[a]; } int main(){ cin m; // 0是左端点，1是右端点 r[0] = 1, l[1] = 0; idx = 2; while (m -- ) { string op; cin op; int k, x; if (op == "L"){ cin x; insert(0, x); } else if (op == "R"){ cin x; insert(l[1], x); } else if (op == "D"){ cin k; remove(k + 1); } else if (op == "IL"){ cin k x; insert(l[k + 1], x); } else{ cin k x; insert(k + 1, x); } } for (int i = r[0]; i != 1; i = r[i]) cout e[i] ' '; cout endl; return 0; }栈AcWing 828. 模拟栈法1：数组模拟栈#includebits/stdc++.h using namespace std; const int N = 100010; int stk[N] ,tt ; int main(){ int m; cin m; while(m--){ int x; string op; cin op; //进栈 if(op == "push"){ cin x; AcWing算法基础课
文章目录前言第一讲 基础算法快速排序归并排序*AcWing 788. 逆序对的数量二分高精度前缀和与差分AcWing 796. 子矩阵的和*AcWing 797. 差分双指针算法位运算离散化区间合并*AcWing 803. 区间合并第二讲 数据结构单链表双链表栈队列单调栈*AcWing 830. 单调栈单调队列*AcWing 154. 滑动窗口(单调队列)KMP(暴力算就行)Trie*AcWing 835. Trie字符串统计(map哈希表应用)并查集*AcWing 837. 连通块中点的数量堆*AcWing 839. 模拟堆(集合模拟堆)哈希表*AcWing 841. 字符串哈希（s.substr(pos, len)比较不同位置子串相等）第三讲 搜索与图论DFS*AcWing 842. 排列数字(全排列n!)BFS*AcWing 844. 走迷宫(数组的二维bfs最短路径)树与图的深度优先遍历AcWing 846. 树的重心(图树双向边一维dfs最短路径)树与图的广度优先遍历*AcWing 847. 图中点的层次(图树有向边一维bfs最短路径)拓扑排序Dijkstrabellman-fordspfaFloydPrimKruskal染色法判定二分图匈牙利算法第四讲 数学知识质数AcWing 866. 试除法判定质数*AcWing 867. 分解质因数*AcWing 868. 筛质数(诶氏筛法)约数*AcWing 869. 试除法求约数(if(x%i == 0),[i,x/i]因子成对出现)AcWing 870. 约数个数*AcWing 872. 最大公约数欧拉函数快速幂扩展欧几里得算法中国剩余定理高斯消元容斥原理博弈论第五讲 动态规划背包问题AcWing 2. 01背包问题 （**1组物品，每个物品只能用一次**）AcWing 3. 完全背包问题 （**1组物品，每个物品可用无限次**）AcWing 4. 多重背包问题 （**1组物品，每个物品最多用k次**）AcWing 9. 分组背包问题 （**n组物品，每组物品只能选一次**）线性DPAcWing 898. 数字三角形AcWing 895. 最长上升子序列 （**子序列可以是不连续的子序列**）AcWing 897. 最长公共子序列 （**A、B两串的最长公共子串c**）AcWing 902. 最短编辑距离(A串变B串需要步骤)区间DPAcWing 282. 石子合并计数类DPAcWing 900. 整数划分数位统计DP状态压缩DP树形DP记忆化搜索AcWing 901. 滑雪第六讲 贪心区间问题AcWing 905. 区间选点 （**每个集合右端点排序**）AcWing 908. 最大不相交区间数量 （每个集合右端点排序，题解同上题）AcWing 906. 区间分组 （每个集合左端点排序）Huffman树AcWing 148. 合并果子 (小堆实现哈夫曼权值)排序不等式AcWing 913. 排队打水 (小堆实现long long res += a * s.size())绝对值不等式AcWing 104. 货仓选址(升序取中点res += | a[i] - a[n/2] |)推公式AcWing 125. 耍杂技的牛(S[i]+W[i]越大放越下面)前言基础知识：C++ 标准库 菜鸟教程系统学习：AcWing算法基础课算题计划：图解算法数据结构【1】AcWing_Plan 一轮：2024.3.12 - 2024.4.26【2】LeetCode_Plan 算法刷题攻略|| 二轮：2024.5.1 – 2024.5.18【3】通关要求：简单/经典/模板题有手就行, 偏题难题选择记忆算法 :搜索、查找、排序、双指针、回溯、分治、动态规划、贪心、位运算数据结构 :数组、栈、队列、字符串、链表、树、图、堆、哈希表等。第一讲 基础算法包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容快速排序AcWing 785. 快速排序//【思路】首尾ij双指针+递归左右排序 #includeiostream using namespace std; //指明命名空间，才能使用cout和endl等C++中的标识符 const int N = 100010;//定义常量，类比C语言的#define int N = 100000; int q[N]; void quick_sort(int q[],int L,int R) { //递归终止条件 if(L = R) return; int i = L-1, j = R+1, x = q[(L+R)1];//初始化变量 //递归执行条件 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_sort(q,j+1,R); } int main() { int n ; scanf("%d",n); for(int i=0; in; i++) scanf("%d",q[i]); quick_sort(q,0,n-1); for(int i=0; in; i++) printf("%d ",q[i]);//"%d "注意题干要求输出格式空格开 return 0; }AcWing 786. 第k个数#includeiostream using namespace std; const int N = 100010; int q[N]; void quick_sort(int q[],int L,int R) { //递归终止条件 if(L = R) return; int i = L-1, j = R+1, x = q[(L+R)1];//初始化变量 //递归执行条件 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_sort(q,j+1,R); } int main() { int n ,k; scanf("%d%d",n,k); for(int i=0; in; i++) scanf("%d",q[i]); quick_sort(q,0,n-1); cout q[k-1] endl;//等价于printf("%d",q[k-1]); return 0; }归并排序AcWing 787. 归并排序//【1】sort大法调用功能库函数 #includeiostream #includealgorithm using namespace std; const int N=100010; int q[N]; int main(){ int n; cin n; for(int i=0;in;i++) cin q[i]; sort(q,q+n); for(int i=0;in;i++) cout q[i] " "; return 0; }#includebits/stdc++.h using namespace std; const int N = 100010; int q[N],tmp[N];//辅助数组tmp void merge_sort(int q[],int l,int r){ //递归终止条件 if(l = r) return; int mid = (l+r) 1; //递归入口 merge_sort(q,l,mid); merge_sort(q,mid+1,r); //递归执行条件 int k=0, i=l, j=mid+1; while(i=mid j=r){ if(q[i] = q[j]) tmp[k++] = q[i++]; else{ tmp[k++] = q[j++]; } } //A指针未到尾部，B指针便利完B数组，A剩余元素直接加到B尾部 while(i=mid) tmp[k++] = q[i++]; while(j=r) tmp[k++] = q[j++]; //递归结果数组复制 for(int i=l,j=0 ; i=r ;i++,j++) q[i] = tmp[j]; } int main(){ int n; cin n; for(int i=0;in;i++) cin q[i]; merge_sort(q,0,n-1); for(int i=0;in;i++) cout q[i] " " ; return 0; }*AcWing 788. 逆序对的数量#includebits/stdc++.h using namespace std; const int N = 100010; int q[N],tmp[N];//辅助数组tmp long long res = 0; void merge_sort(int q[],int l,int r){ //递归终止条件 if(l = r) return; int mid = (l+r) 1; //递归入口 merge_sort(q,l,mid); merge_sort(q,mid+1,r); //递归执行条件 int k=0, i=l, j=mid+1; while(i=mid j=r){ //分治思想 if(q[i] = q[j]) tmp[k++] = q[i++]; else{ tmp[k++] = q[j++]; res += mid-i+1;//当ij且q[i]q[j]符合题意，满足数量为mid-i+1 } } //A指针未到尾部，B指针便利完B数组，A剩余元素直接加到B尾部 while(i=mid) tmp[k++] = q[i++]; while(j=r) tmp[k++] = q[j++]; //递归结果数组复制 for(int i=l,j=0 ; i=r ;i++,j++) q[i] = tmp[j]; } int main(){ int n; cin n; for(int i=0;in;i++) cin q[i]; merge_sort(q,0,n-1); cout res endl ; return 0; }法2：冒泡排序暴力(会超时)#include bits/stdc++.h using namespace std; const int N = 1e5+10; int q[N]; int main(){ int n ; cin n; for (int i = 0 ; i n ; i ++) cin q[i]; int res = 0; for (int i = 0; i n ; i++) for(int j = i+1; j n ; j ++) if(q[i] q[j]) res++; cout res endl; return 0; }二分AcWing 789. 数的范围#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N]; int main(){ int n,q; cin n q; for(int i=0;in;i++) cin a[i]; while(q--){ int k; cin k; int x1,x2; //eg. a[1,2,2,3,3,4]、K=3、【x1=3 , x2=5-1=4】= res = [3,4] // K=5、【x1=5 , x2=5-1=4】= res = [-1,-1] x1 = lower_bound(a, a + n, k) - a;//找第一个=k的位置,找不到返回end x2 = upper_bound(a, a + n, k) - a - 1;//找第一个k的位置 if(x1 == x2+1) printf("-1 -1\n"); else printf("%d %d\n",x1,x2); } return 0; }法2；常规二分法#includeiostream using namespace std; int a[100010]; int n,q; int main(){ scanf("%d%d",n,q); for(int i=0;in;i++) scanf("%d",a[i]); while(q--) { int k; scanf("%d",k); //找k出现的起始位置 int l=0,r=n-1; while(lr){ int mid=l+r1; if(a[mid]=k) r=mid; else l=mid+1; } //没找到 if(a[l]!=k) printf("-1 -1\n"); //找k出现的的终止位置 else { printf("%d ",l); int l=0,r=n-1; while(lr){ int mid=l+r+11; if(a[mid]=k) l=mid; else r=mid-1; } printf("%d\n",l); } } return 0; }AcWing 790. 数的三次方根法1；调用cbrt()开立方根函数 //cbrt(-27.00) = -3.00#includebits/stdc++.h using namespace std; int main(){ double n; cin n; printf("%.6lf\n",cbrt(n)); return 0; }法2；常规二分法#include iostream using namespace std; int main() { double x; cin x; double l = -100, r = 100; while (r - l 1e-8) { double mid = (l + r) / 2; if (mid * mid * mid = x) r = mid; else l = mid; } printf("%.6lf\n", l); return 0; }高精度AcWing 791. 高精度加法#includebits/stdc++.h using namespace std; const int N = 110; int a[N],b[N],c[N]; int main(){ string s1,s2; cin s1 s2; //reverse（）函数用来翻转数组，字符串，向量； reverse(s1.begin(),s1.end()); //reverse(s1.begin(),s1.end()); 翻转整个字符串 reverse(s2.begin(),s2.end()); //reverse(s.begin()+i,s.begin()+k); 翻转下标i到k（不包含k） for(int i = 0;i s1.size();i++) a[i] = s1[i] - 48; for(int i = 0;i s2.size();i++) b[i] = s2[i] - 48; int len = max(s1.size(), s2.size()); int jinwei = 0; for(int i = 0;i len;i++){ c[i] = a[i] + b[i] + jinwei; jinwei = c[i] / 10; c[i] = c[i] % 10; } if(jinwei == 1) cout "1"; for(int i = len - 1;i = 0;i--) cout c[i]; return 0; }AcWing 792. 高精度减法#includeiostream using namespace std; int a[100010],lena,b[100010],lenb,c[100010],lenc; string A,B; void div(int a[],int b[]){ lenc=max(lena,lenb); for(int i=0;ilenc;i++){#includeiostream using namespace std; int a[100010],lena,b[100010],lenb,c[100010],lenc; string A,B; void div(int a[],int b[]){ lenc=max(lena,lenb); for(int i=0;ilenc;i++){ c[i]+=a[i]-b[i]; if(c[i]0){ c[i+1]--; c[i]+=10; } } while(!c[lenc-1]lenc1) lenc--; } bool bigger(){ if(lenalenb) return true; if(lenblena) return false; for(int i=lena-1;i=0;i--) if(a[i]b[i]) return true; else if(b[i]a[i]) return false; return true; } int main(){ cinAB; lena = A.size(),lenb = B.size(); for(int i=0;ilena;i++) a[i]=A[lena-1-i]-'0'; for(int i=0;ilenb;i++) b[i]=B[lenb-1-i]-'0'; if(bigger()) div(a,b); else{printf("%c",'-'); div(b,a);} for(int i=lenc-1;i=0;i--) printf("%d",c[i]); } c[i]+=a[i]-b[i]; if(c[i]0){ c[i+1]--; c[i]+=10; } } while(!c[lenc-1]lenc1) lenc--; } bool bigger(){ if(lenalenb) return true; if(lenblena) return false; for(int i=lena-1;i=0;i--) if(a[i]b[i]) return true; else if(b[i]a[i]) return false; return true; } int main(){ cinAB; lena=A.size(),lenb=B.size(); for(int i=0;ilena;i++) a[i]=A[lena-1-i]-'0'; for(int i=0;ilenb;i++) b[i]=B[lenb-1-i]-'0'; if(bigger()) div(a,b); else{printf("%c",'-'); div(b,a);} for(int i=lenc-1;i=0;i--) printf("%d",c[i]); }AcWing 793. 高精度乘法#include bits/stdc++.h using namespace std; vectorint mul(vectorint A, int b) { vectorint C; int t = 0; for (int i = 0; i A.size() || t; i ++ ){ if (i A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() 1 C.back() == 0) C.pop_back(); return C; } int main(){ string a; int b; cin a b; vectorint A; for (int i = a.size()-1; i = 0; i--) A.push_back(a[i] - '0'); auto C = mul(A, b); for (int i = C.size()-1; i = 0; i--) printf("%d", C[i]); return 0; }AcWing 794. 高精度除法#include bits/stdc++.h using namespace std; vectorint div(vectorint A, int b, int r) { vectorint C; r = 0; for (int i = A.size() - 1; i = 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() 1 C.back() == 0) C.pop_back(); return C; } int main() { string a; vectorint A; int B; cin a B; for (int i = a.size()-1; i = 0; i--) A.push_back(a[i] - '0'); int r; auto C = div(A, B, r); for (int i = C.size()-1; i = 0; i--) cout C[i]; cout endl r endl; return 0; }前缀和与差分AcWing 795. 前缀和#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N],s[N]; int main(){ int n,m; cin n m; for(int i=1;i=n;i++) cin a[i]; for(int i=1;i=n;i++) s[i] = s[i-1] + a[i];//前缀和初始化 while(m--){ int l,r; cin l r; cout s[r]-s[l-1] endl;//区间和计算 } return 0; }AcWing 796. 子矩阵的和#includebits/stdc++.h using namespace std; const int N = 1010; int s[N][N]; int main(){ int n,m,q; cin n m q; for(int i=1;i=n;i++) for(int j=1;j=m;j++){ cin s[i][j]; s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];//二维矩阵初始化 } while(q--){ int x1,y1,x2,y2; scanf("%d%d%d%d",x1,y1,x2,y2); //二维前缀和 printf("%d\n",s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]); } return 0; }*AcWing 797. 差分问题：给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c , a[r] + c;写法一：#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N],b[N]; int main(){ int n,m; cin n m; for(int i=1;i=n;i++){ cin a[i]; b[i] = a[i] - a[i-1];//初始化差分数组,默认a[0]=0 } while(m--){ int l,r,c; cin l r c; b[l] += c; //将序列中[l, r]之间的每个数都加上c b[r+1] -= c; } for(int i=1;i=n;i++){ a[i] = a[i-1] + b[i];//前缀和运算 cout a[i] " " ; } return 0; }写法二：#includebits/stdc++.h using namespace std; const int N = 100010; int a[N],b[N]; void insert(int l,int r,int c){ b[l] += c; b[r+1] -= c; } int main(){ int n,m; cin n m; for(int i=1;i=n;i++){ cin a[i]; insert(i,i,a[i]);//初始化差分数组,默认a[0]=0 } while(m--){ int l,r,c; scanf("%d%d%d",l,r,c); insert(l,r,c);//将序列中[l, r]之间的每个数都加上c } for(int i=1;i=n;i++) { b[i] += b[i-1];//差分操作指定段数组 cout b[i] " "; } return 0; }AcWing 798. 差分矩阵#includebits/stdc++.h using namespace std; const int N = 1010; int a[N][N], b[N][N]; //差分插入操作 void insert(int x1, int y1, int x2, int y2, int c) {//对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main(){ int n, m, q; cin n m q; for (int i = 1; i = n; i ++) for (int j = 1; j = m; j ++){ cin a[i][j]; insert(i, j, i, j, a[i][j]);//初始化差分矩阵 } while (q -- ){ int x1, y1, x2, y2, c; scanf("%d%d%d%d%d",x1,y1,x2,y2,c); insert(x1, y1, x2, y2, c);//构建差分矩阵 } for (int i = 1; i = n; i ++){ for (int j = 1; j = m; j ++) { b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];//进行差分操作 cout b[i][j] " " ; //输出差分后的结果 } printf("\n");//换行输出 } return 0; }双指针算法AcWing 799. 最长连续不重复子序列#includebits/stdc++.h using namespace std; const int N=100010; int a[N],s[N]; //a存数据，b作为桶记录每个数字出现的次数 int main(){ int n; cin n; for(int i=0;in;i++) cin a[i]; int res=0; for(int i=0,j=0;in;i++) { s[a[i]]++; //指向一个数，对应数的出现次数+1 while(ji s[a[i]]1) { //s[a[i]]1,说明当前区间有重复元素a[i]. s[a[j]]--; //把j对应位置的数删掉, j指针向前走 j++; } res=max(res,i-j+1); //每轮取当前连续区间长度的max } cout res endl; return 0; }AcWing 800. 数组元素的目标和 给定两个升序排序的有序数组 A 和 B，以及一个目标值 x, 数组下标从 0开始。 请你求出满足 A[i]+B[j]=𝑥 的数对 (𝑖,𝑗) . 数据保证有唯一解。#includebits/stdc++.h using namespace std; const int N = 1e5+10; int a[N],b[N]; int main(){ int n,m,x; cin n m x; for(int i=0; in; i++) cin a[i]; for(int i=0; im; i++) cin b[i]; //i-A[0]、j-B[m-1] ,j只能往左移 for(int i=0,j=m-1; in; i++) { while(j = 0 a[i]+b[j] x) j--; //a[i]+b[j]x, AB数组升序，只能j指针往左移 if(j = 0 a[i]+b[j] == x) printf("%d %d\n",i,j); //走到j i时, i指针往右移继续判断，题干可以确定有唯一值 } return 0; }AcWing 2816. 判断子序列#includebits/stdc++.h using namespace std; const int N = 100010; int a[N],b[N]; int main(){ int n,m; cin n m; for(int i=0;in;i++) cin a[i]; for(int i=0;im;i++) cin b[i]; int i = 0; for(int j = 0; j m; j++){//a[i]!=b[j],j右移一位继续匹配 if(i n a[i] == b[j]) i++; } if(i == n) puts("Yes"); //i=n跳出循环,找到b中子序列a else puts("No"); return 0; }位运算AcWing 801. 二进制中1的个数法1：STL库 bst.count()函数#includebits/stdc++.h using namespace std; int main(){ int n; cin n; int arr[n]; for(int i=0; in ;i++) cin arr[i]; for(int i=0; in ;i++){ bitset32 bst(arr[i]); //bitset32 bst(0xffff);定义bst数组共有32位,把bst中0~15低位置为1,剩余高位置0 cout bst.count() " "; } return 0; }法2：#include bits/stdc++.h using namespace std; //返回N的最后一位1 = n(-n) int lowbit(int x) {//正数x的反码为-x，补码为取反+1 return x (-x);//x -x == x (~x +1) } int main(){ int n; cin n; while (n -- ){ int x; cin x; int res = 0; while(x){ x -= lowbit(x);//每次减去x的最后一位1 res ++;//1个数更新 } cout res " "; } return 0; }离散化AcWing 802. 区间和法1：#include iostream #include vector #include algorithm using namespace std; const int N = 300010; //n次插入和m次查询相关数据量的上界 int n, m; int a[N];//存储坐标插入的值 int s[N];//存储数组a的前缀和 vectorint alls; //存储（所有与插入和查询有关的）坐标 vectorpairint, int add, query; //存储插入和询问操作的数据 int find(int x) { //返回的是输入的坐标的离散化下标 int l = 0, r = alls.size() - 1; while (l r) { int mid = l + r 1; if (alls[mid] = x) r = mid; else l = mid + 1; } return r + 1; } int main() { scanf("%d%d", n, m); for (int i = 1; i = n; i++) { int x, c; scanf("%d%d", x, c); add.push_back({x, c}); alls.push_back(x); } for (int i = 1; i = m; i++) { int l , r; scanf("%d%d", l, r); query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } //排序，去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); //执行前n次插入操作 for (auto item : add) { int x = find(item.first); a[x] += item.second; } //前缀和 for (int i = 1; i = alls.size(); i++) s[i] = s[i-1] + a[i]; //处理后m次询问操作 for (auto item : query) { int l = find(item.first); int r = find(item.second); printf("%d\n", s[r] - s[l-1]); } return 0; }法2：思路： 因为范围太大， 所以不能开一个大数组//开一个小数组 : 范围就是 add(index) + question(index) ， 两者的范围， 排序去重//我们在index + c, 就是要在新数组的新下标下标操作#includebits/stdc++.h using namespace std; const int N = 1000010; int a[N], s[N]; typedef pairint, int pii; int main(){ int n, m; cin n m; vectorpii add, query; vectorint all; for(int i = 0; i n; i++) { int l , r; cin l r; add.push_back({l, r}); //存储单独一个 all.push_back(l); } for(int i = 0; i m; i++) { int l , r; cin l r; all.push_back(l); all.push_back(r); query.push_back({l, r}); } // 去重 sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); //去重 //获取新下标 unordered_mapint, int get_index; for(int i = 1; i = all.size(); i++) get_index[all[i-1]] = i;//注意这里 all[i-1],不是i // 处理插入 for(int i = 0; i add.size(); i ++) { int old_index = add[i].first; int c = add[i].second; int new_index = get_index[old_index]; a[new_index] += c; } // 预处理前缀和 for(int i = 1; i = all.size(); i++) a[i] += a[i - 1]; // 处理询问 for(auto p : query) { int l = p.first, r = p.second; int l2 = get_index[l], r2 = get_index[r]; cout (a[r2] - a[l2 - 1]) endl; } return 0; }区间合并*AcWing 803. 区间合并法1:#includebits/stdc++.h using namespace std; const int N = 100100; int n,cnt;//cnt为初始满足条件的区间个数 pairint,int a[N]; //类似结构体A[N]={(1，2),(1，2)...} int main(){ //输入数据 cin n; for(int i=1; i=n; i++) cin a[i].first a[i].second; //每个集合左端点排序 sort(a+1,a+1+n); //依次遍历开始比较 cnt = n; for(int i=1; in ; i++){ //相邻两集合 有交集 或 为父子集 if(a[i].second = a[i+1].first){ cnt --; a[i+1].first = a[i].first; a[i+1].second = max(a[i+1].second, a[i].second); } //相邻两集合 无交集 else continue; } //输出结果 cout cnt endl; return 0; }✔法2：贪心模板#includebits/stdc++.h using namespace std; const int N=1e5+10; typedef pairint,int PII; PII a[N]; int main(){ int n; cinn; for(int i=0;in;i++) cin a[i].first a[i].second; sort(a,a+n);//每个集合左端点排序 int end = a[0].second, res = 1;//初始排好序的第1个集合算1个区间 for(int i=1;in;i++){ //相邻两集合 无交集 if(end a[i].first){ res++; end = a[i].second; } //相邻两集合 有交集 或 为父子集 else end = max(end, a[i].second); } cout res endl; return 0; }第二讲 数据结构包括单链表，双链表，栈，队列，单调栈，单调队列，KMP，Trie，并查集，堆，哈希表等内容单链表AcWing 826. 单链表#includebits/stdc++.h using namespace std; const int N = 1e5+10; int head,e[N],ne[N],idx; //head头节点下标, e[i]节点i的值, ne[i]节点i的next指针, idx存储当前指向的点 //初始化 void init(){ head = -1; idx = 0; } //头插操作 void add_to_head(int x){ e[idx] = x; ne[idx] = head; head = idx++; } //后插x操作 void add(int k,int x){ e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } // 删头结点，需要保证头结点存在 void remove_head(){ head = ne[head]; } //删除下标为k的下一个点 void remove(int k){ ne[k] = ne[ne[k]]; } int main(){ int m; cin m; init(); while(m--){ char op;int k,x; cin op; if(op == 'H'){//头插操作 cin x; add_to_head(x); } if(op == 'I'){//后插操作 cin k x; add(k-1,x);//第k个数，下标从0开始算 } if(op == 'D'){//后删操作 cin k; if(k == 0) remove_head();//删除头节点 else remove(k-1);//第k个数，下标从0开始算 } } for(int i=head; i != -1; i = ne[i]) cout e[i] " "; return 0; }双链表AcWing 827. 双链表#include bits/stdc++.h using namespace std; const int N = 100010; int m; int e[N], l[N], r[N], idx; // 在节点a的右边插入一个数x void insert(int a, int x){ e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = idx ++ ; } // 删除节点a void remove(int a){ l[r[a]] = l[a]; r[l[a]] = r[a]; } int main(){ cin m; // 0是左端点，1是右端点 r[0] = 1, l[1] = 0; idx = 2; while (m -- ) { string op; cin op; int k, x; if (op == "L"){ cin x; insert(0, x); } else if (op == "R"){ cin x; insert(l[1], x); } else if (op == "D"){ cin k; remove(k + 1); } else if (op == "IL"){ cin k x; insert(l[k + 1], x); } else{ cin k x; insert(k + 1, x); } } for (int i = r[0]; i != 1; i = r[i]) cout e[i] ' '; cout endl; return 0; }栈AcWing 828. 模拟栈法1：数组模拟栈#includebits/stdc++.h using namespace std; const int N = 100010; int stk[N] ,tt ; int main(){ int m; cin m; while(m--){ int x; string op; cin op; //进栈 if(op == "push"){ cin x;