Loading... 基本数据结构 <!--more--> ====== 栈 - * STL：stack * 定义：stack a; * 查询堆顶：a.top(); * 压入栈顶:a.pop(); * 查询a中的元素个数：a.size(); * 清空只能慢慢pop。 #### 例题1 * 给定一个栈，维护三个操作。 1：将一个数x压入栈中。 2：求栈中数的最大值。 3：弹出栈顶的数。 Q<=1000。 Q<=100000。 #### 例题2 * 给定一个栈，维护四个操作。 1：将一个数x压入栈中。 2：求栈中数的最大值。 3：弹出栈顶的数。 4：求栈中的栈底开始的最大前缀和。 Q<=1000。 Q<=100000。 #### 例题3 * 给定一个栈，维护五个操作。 1：将一个数x压入栈中。 2：求栈中数的最大值。 3：弹出栈顶的数。 4：求栈中的栈底开始的最大前缀和。 5：求栈中的栈顶开始的最大前缀和。 总和-栈底开始的最小前缀和 Q<=1000。 Q<=100000。 #### 例题4 * 给定一个数列，维护五个操作。 1：在光标的后面插入一个数字。 2：删除光标前的最后一个数字。 3：左移光标。 4：右移光标。 5：求光标前的最大前缀和。 Q<=1000。 Q<=100000。 ##### 栈的一些其它应用 * 有n个数排成一列，每次可以选择最前面的数压入栈，或者弹出栈顶的元素。 求不同的出栈序列方案总数。 例如当n=3时共有5个不同的出栈序列方案：123,132,213,231,321. * 卡特兰数！ 队列 -- * queue： * 定义：queue a; 插入队尾：a.push(x); 删除队首：a.pop(); 查询队尾：a.back(); 查询队首：a.front(); 查询长度：a.size(); 清空只能慢慢pop。 * deque： * 定义：deque a; 插入队尾：a.push\_back(x); 插入队首：a.push\_front(x); 删除队首：a.pop\_front(); 删除队尾：a.pop\_back(); 查询队尾：a.back(); 查询队首：a.front(); 查询长度：a.size(); 清空：a.clear(); #### 例题1 * 给定一个队列，维护三个操作。 1：将一个数x压入队列中。 2：求队列中数的最大值。 3：弹出队列的数。 Q<=1000。 Q<=100000。 include <bits/stdc++.h> using namespace std; int main() { deque <int> a,b; //a值，b时间戳 for (i=1; i<=Q; i++) { cin>>A; if (A==1) //每执行A==1 都会使a.size+1 { cntI++; cin>>x; while (a.back()<=x) a.pop_back(),b.pop_back(); //每执行这个while，都会使a.size减-1 a.push_back(x); b.push_back(cntI); } if (A==2) cout<<a.front()<<endl; if (A==3) { cntD++; if (cntD == b.front()) a.pop_front(),b.pop_front(); } } return 0; } O(Q) ### 单调队列 * 在每次进入队伍时，判断当前元素与队尾元素的大小关系，若小于队尾元素，则队尾不可能成为最小值，直接删除即可。 每次查询的答案一定在队首位置。 由于每个元素至多进队列和出队列一次，时间复杂度为O(n)。 #### 例题1 * 给定一个队列，维护五个操作。 1：将一个数x压入队列中。 2：求队列中数的最大值。 3：弹出队列的数。 4：求队列中的最大前缀和。 5：求队列中的最大后缀和。 = 总和 - 最小前缀和 Q<=1000。 Q<=100000。 #### 例题2——广告印刷 * 有n个数ai。从中选出一段区间\[L,R\]，使得(R-L+1)*min{a\_L,…,a\_R}最大。 n<=100000。 * **思路：**枚举最小值a\[i\]，之后向右找最远扩展到哪里，右边最近的且比a\[i\]小的 * 对于每个i，都在右边找一个最近且比a\[i\]小的。 这件事情可以用单调队列解决。 * 考虑对于第i个数，求出当这个数成为最小值时，往左往右分别最远能到哪里。 用这些来更新答案就可以了。 使用单调队列来实现这一过程。 #### 例题3 * 给定n*m的01矩阵 找一个面积最大的全0子矩阵。 $n,m\\leq1000$ `cpp if (a[i][j]==0) f[i][j] = f[i-1][j] + 1; else f[i][j] = 0;` RMQ问题 ----- * 给定n个数，有Q次询问，每次询问一段区间的最小值。 * 倍增。 nlgn 1 线段树。 n lgn 分块。 nsqrtn sqrtn 整体二分。 * 倍增：记录所有长度为2的幂次的区间的最小值。 n=5 \[1,1\] \[2,2\] \[3,3\] \[4,4\] \[5,5\] \[1,2\] \[2,3\] \[3,4\] \[4,5\] \[1,4\] \[2,5\] f\[i\]\[j\] 表示 \[i,i+2^j-1\] 这段区间的最小值 \[2,5\] f\[2\]\[2\] nlgn项 f[i][0] = a[i] f[i][j]表示[i,i+2^j-1]这段区间的最小值 f[i][j] = min(f[i][j-1],f[i+(1<<j-1)][j-1]) for (j=1; j<=20; j++) for (i=1; i<=n-(1<<j)+1; i++) f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]) [L,R] 先找到一个k，使得2^k <= R-L+1 且 2^(k+1) > R-L+1 一开始预处理 p[x] 表示当R-L+1=x时k应该是多少 k=int(log(R-L+1)/log(2)) k=p[R-L+1]; min(f[L][k],f[R-(1<<k)+1][k]) 开车旅行 * 我们考虑记录a\[x\]~a\[x+2^k-1\]的最小值，令其为f\[x\]\[k\]。这可以在nlgn的时间内求出。 对于每次询问L~R，令k=log\[R-L+1\]。有ans=min(f\[L\]\[k\],f\[R-2^k+1\]\[k\])。(即进行O(1)询问) LCA --- * 给定一棵树，求两个点的最近公共祖先。 通过倍增来求LCA。 * **思路：** 1.将两个点深度变成一样。 2. 一起往上走找最近公共祖先。 * 事先得先求出每个点的父亲是谁，以及它的深度是多少。 * dfs * fa\[i\]表示i的父亲，dep\[i\]表示i的深度 第一步：将x和y走到同一层。 if (dep\[x\]<dep\[y\]) swap(x,y); // 保证dep\[x\]>=dep\[y\] 意味着 x要向上走dep\[x\]-dep\[y\]步。 * f\[i\]\[j\] 表示 i向上走2^j步后，能到哪儿 f\[i\]\[0\]=fa\[i\]; f\[i\]\[j\]=f\[f\[i\]\[j-1\]\]\[j-1\] for (j=1; j<=20; j++) for (i=1; i<=n; i++) f\[i\]\[j\]=f\[f\[i\]\[j-1\]\]\[j-1\] 通过f数组来加速x向上走这个过程。 * x向上走dep\[x\]-dep\[y\]步。 t=dep\[x\]-dep\[y\] 将t二进制分解 10 = 1010 x先向上跳8步，再向上跳2步 for (i=20; i>=0; i--) if (t&(1<<i)) x=f\[x\]\[i\]; x和y就会到达同一层 让x和y一起往上跳，找它们的最近公共祖先 for (i=20; i>=0; i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i] if (x==y) return x; else return f[x][0]; * 预处理fa，dep f[i][0]=fa[i]; f[i][j]=f[f[i][j-1]][j-1] for (j=1; j<=20; j++) for (i=1; i<=n; i++) f[i][j]=f[f[i][j-1]][j-1] t=dep[x]-dep[y] for (i=20; i>=0; i--) if (t&(1<<i)) x=f[x][i]; //这一步结束时有可能x==y if (x==y) return x; for (i=20; i>=0; i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i] return f[x][0]; * dfs void dfs(int x,int y) { dep[x]=y; for (i=son of x) {fa[i]=x; dfs(i,y+1);} } dfs(1,1); #### 链上最大值问题 * 给定一棵带边权的树，每次询问两个点x,y，求这两个点的路径上最长的边是多少。 * **思路：** f\[i\]\[j\]从i出发向上走2^j步能走到哪儿 g\[i\]\[j\]从i出发向上走2^j步的过程中经过的最长边是什么 * f\[i\]\[0\]=fa\[i\],g\[i\]\[0\]=dis(i,fa\[i\]); f\[i\]\[j\]=f\[f\[i\]\[j-1\]\]\[j-1\] g\[i\]\[j\]=max(g\[i\]\[j-1\],g\[f\[i\]\[j-1\]\]\[j-1\]). 求答案的时候，用g数组来更新最大值 #### 链上和问题 * 给定一棵树，每次询问两个点x,y，求这条路径上边权和是多少。 * **思路：** dis\[i\] 从根节点出发到i经过的边的长度和 x~y的路径长度 dis\[x\]+dis\[y\] – 2*dis\[LCA(x,y)\] #### 链上异或问题 * 给定一棵树，每次询问两个点x,y，求这条路径上边权异或和是多少。 * **思路：** dis\[i\]表示从1出发到i经过的边的边权亦或和 x~y = dis\[x\]^dis\[y\] Hash ---- ### 简单Hash * 有100个数字，每个数字的大小都是$\\leq10^5$。 问是否存在一对数字的值相等。 要求一个线性做法。 for (i=1; i<=100; i++) { cin>>A; f[A]++; if (f[A]==2) return true; } return false; * $\\leq10^9$ 呢？ for (i=1; i<=100; i++) { cin>>A; A%=12345678; f[A]++; if (f[A]==2) return true; } return false; #### 重要性质 * 假如有n个自然数。 要使得这n个数之间在大概率下不冲突(不同的数在模p意义下相等)。 p>=n^2。 ### 一维Hash void Insert(int x) { int t=x % 19999997; //a[i]来表示i这个位置存的数是什么 while (a[t] && a[t]!=x) t=(t+1) % 19999997; a[t]=x; b[t]++; // b[i]表示a[i]这个数字出现了几次 } int Query(int x) { int t=x % 19999997; while (a[t] && a[t]!=x) t=(t+1) % 19999997; if (a[t]==x) return b[t]; else return 0; } cin>>A; Insert(A); if (Query(A)==2) return true; * 模数开成10倍的元素个数，近似线性 ### 字符串Hash * 给定一个字符串，求是否存在两个长度为k的子串完全相同。 * abcabc k=4 * 要求$O(|s|)$ * |s|<=100W 对于每一个数字 先对10^18取模 得到 n-k+1个 10^18级别的数，询问是否存在一对数相同 两次hash 第一次hash -> 很大的26进制数 变成 10^18级别的数 二次 -> 10^18级别的数映射到1000W级别的数组 ### 二维Hash * 给定一个n_n的矩阵，求是否存在两个完全相同的k_k的子矩阵。 要求时间复杂度与读入同阶。 Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏