前言

• 基础知识：C++ 标准库 菜鸟教程
• 系统学习：AcWing算法基础课
• 算题计划：图解算法数据结构
  【1】AcWing_Plan 一轮：2024.3.12 - 2024.4.26
  【2】LeetCode_Plan 算法刷题攻略|| 二轮：2024.5.1 – 2024.5.18
  【3】通关要求：简单/经典/模板题有手就行, 偏题难题选择记忆
  算法 :搜索、查找、排序、双指针、回溯、分治、动态规划、贪心、位运算
  数据结构 :数组、栈、队列、字符串、链表、树、图、堆、哈希表等。

第一讲 基础算法

包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容

快速排序

AcWing 785. 快速排序

//【思路】首尾ij双指针+递归左右排序 #include<iostream> 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(i<j){ do i++; while(q[i]<x); do j--; while(q[j]>x); if(i<j) 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; i<n; i++) scanf("%d",&q[i]); quick_sort(q,0,n-1); for(int i=0; i<n; i++) printf("%d ",q[i]);//"%d "注意题干要求输出格式空格开 return 0; }

AcWing 786. 第k个数

#include<iostream> 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(i<j){ do i++; while(q[i]<x); do j--; while(q[j]>x); if(i<j) 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; i<n; 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大法调用功能库函数 #include<iostream> #include<algorithm> using namespace std; const int N=100010; int q[N]; int main(){ int n; cin >> n; for(int i=0;i<n;i++) cin >> q[i]; sort(q,q+n); for(int i=0;i<n;i++) cout << q[i] << " "; return 0; }

#include<bits/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;i<n;i++) cin >> q[i]; merge_sort(q,0,n-1); for(int i=0;i<n;i++) cout << q[i] << " " ; return 0; }

*AcWing 788. 逆序对的数量

#include<bits/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;//当i<j且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;i<n;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. 数的范围

#include<bits/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;i<n;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；常规二分法

#include<iostream> using namespace std; int a[100010]; int n,q; int main(){ scanf("%d%d",&n,&q); for(int i=0;i<n;i++) scanf("%d",&a[i]); while(q--) { int k; scanf("%d",&k); //找k出现的起始位置 int l=0,r=n-1; while(l<r){ int mid=l+r>>1; 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(l<r){ int mid=l+r+1>>1; 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

#include<bits/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. 高精度加法

#include<bits/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. 高精度减法

#include<iostream> 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;i<lenc;i++){#include<iostream> 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;i<lenc;i++){ c[i]+=a[i]-b[i]; if(c[i]<0){ c[i+1]--; c[i]+=10; } } while(!c[lenc-1]&&lenc>1) lenc--; } bool bigger(){ if(lena>lenb) return true; if(lenb>lena) 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(){ cin>>A>>B; lena = A.size(),lenb = B.size(); for(int i=0;i<lena;i++) a[i]=A[lena-1-i]-'0'; for(int i=0;i<lenb;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]&&lenc>1) lenc--; } bool bigger(){ if(lena>lenb) return true; if(lenb>lena) 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(){ cin>>A>>B; lena=A.size(),lenb=B.size(); for(int i=0;i<lena;i++) a[i]=A[lena-1-i]-'0'; for(int i=0;i<lenb;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; vector<int> mul(vector<int> &A, int b) { vector<int> 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; vector<int> 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; vector<int> div(vector<int> &A, int b, int &r) { vector<int> 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; vector<int> 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. 前缀和

#include<bits/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. 子矩阵的和

#include<bits/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;

写法一：

#include<bits/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; }

写法二：

#include<bits/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. 差分矩阵

#include<bits/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. 最长连续不重复子序列

#include<bits/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;i<n;i++) cin >> a[i]; int res=0; for(int i=0,j=0;i<n;i++) { s[a[i]]++; //指向一个数，对应数的出现次数+1 while(j<i && 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]=𝑥 的数对 (𝑖,𝑗) . 数据保证有唯一解。

#include<bits/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; i<n; i++) cin >> a[i]; for(int i=0; i<m; i++) cin >> b[i]; //i->A[0]、j->B[m-1] ,j只能往左移 for(int i=0,j=m-1; i<n; 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. 判断子序列

#include<bits/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;i<n;i++) cin >> a[i]; for(int i=0;i<m;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()函数

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; int arr[n]; for(int i=0; i<n ;i++) cin >> arr[i]; for(int i=0; i<n ;i++){ bitset<32> bst(arr[i]); //bitset<32> 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的前缀和 vector<int> alls; //存储（所有与插入和查询有关的）坐标 vector<pair<int, 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, 就是要在新数组的新下标下标操作

#include<bits/stdc++.h> using namespace std; const int N = 1000010; int a[N], s[N]; typedef pair<int, int> pii; int main(){ int n, m; cin >> n >> m; vector<pii> add, query; vector<int> 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_map<int, 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:

#include<bits/stdc++.h> using namespace std; const int N = 100100; int n,cnt;//cnt为初始满足条件的区间个数 pair<int,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; i<n ; 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：贪心模板

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef pair<int,int> PII; PII a[N]; int main(){ int n; cin>>n; for(int i=0;i<n;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;i<n;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. 单链表

#include<bits/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：数组模拟栈

#include<bits/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;