5.1 最后更新于 2025-05-01 20:27:50

# 数据结构 ### 1.队列&栈 ~~太简单了hh~~ ##### 创建栈：stack<数据类型> 变量名 ##### 队列：queue<数据类型> 变量名 ##### 常用指令：push(xx),pop,size,front（后面一定要加()，char类型push()里要加插入的东西） ```cpp struct queue{ int a[1000]; int head=1,tail=0; void push(int x){ a[++tail]=x; } void pop(){ head++; } int front(){ return a[head]; } int size(){ return tail-head+1; } }; int main(){ return 0; } ``` ### 2.单调队列 ##### 例题[滑动窗口](https://www.luogu.com.cn/problem/P1886) ##### 我就不多说啥了，自己看看就行 ~~我也不会讲啊~~ ### 3.单调栈 ##### 这玩意纯lj（钟神说的，别打我）[猜猜是啥](https://www.luogu.com.cn/problem/P5788) ### 4.堆 ##### 和队列&栈差不多，分为大根堆和小根堆 ##### 创建堆：priority_queue<数据类型> 变量名 ##### 大根堆：常用，取最大值 ##### 小根堆：由大根堆转，有两种方法 #### 方法一： ##### 直接在插入值前加负号 #### 方法二： ##### 创建堆代码中的<数据类型>改为<数据类型，vector<数据类型>,greater<数据类型> >即可 #### 附代码： ```cpp #include<queue> //#include<bits/stdc++.h> using namespace std; priority_queue<int> q; //大根堆 //小根堆最简单的方法：取负号 struct rec { int a,b; }; //如果要把结构体 放入 stl比大小 只能重载小于号 bool operator<(const rec &x,const rec &y) { return x.a + x.b > y.a + y.b; } priority_queue<rec> qq;//取出a+b最小的结构体 int main() { q.push(233); q.push(2233);//向堆里面加入一个元素 q.pop();//从堆中删除一个元素 删除是堆中最大的元素 2233 void类型没有返回值 int x = q.top();//获取堆中最大元素 233 cout << q.size() << endl;//获取堆剩余的元素个数 1 } ``` ### 5.手写堆（我不会） ##### ~~问为什么不讲手写栈和手写队列，因为都差不多~~ ##### 这货和二叉树差不多 ##### 如果有右儿子，就一定有左儿子 ##### 插入一个数到末尾，如果这个数比它的父亲大，那么交换（swap） ##### 时间复杂度：O(logn) ### 6.左移右移位运算 ##### 稍稍插入一点位运算的东西xx ##### $x>>y==x/2^y$ ##### $x<<y == x*2^y$ ### 7.并查集 ##### 所谓并查集，即是合并集合&查询集合中的值，简称并查集 ##### 先把每个东西的箭头指向自身 ##### 从某个点出发，看最后会走到哪里 ##### 合并：赋值一个集合=另一个集合 ##### 查询：查询某个值是否在某个集合 ### 核心代码（find）： ```cpp int find(int x){ if(x!=f[x]) f[x]=find(f[x]); return f[x]; } ``` ## 记住：正难则反!!!(及好用) ### 习题 #### [P3528 [POI 2011] PAT-Sticks](https://www.luogu.com.cn/problem/P3528) #### [P1168 中位数](https://www.luogu.com.cn/problem/P1168) 更多请见https://www.luogu.com.cn/problem/list ### 8.异或 ##### C++中式子：a^b ##### 性质：将两个数转化为二进制，每两相对位都进行异或运算，如果两位数字不同，值为1，如果相同，值为0 ##### 公式：a[l]^a[l+1]^…^a[r]=(a[1]^a[2]^...^a[l-1])^(a[1]^a[2]^...^a[r]) ### 9.字典树Trie ##### 字典树指的是某个字符串集合构造的有根树。字典树较好的利用了字符串的公共前缀，因此有效的节约存储空间 ##### 典型应用是统计、排序和保存大量的字符串(不仅局限于字符串) ##### 三个基本性质： ##### 1、根结点不包含字符，除根结点外每一个节点都只包含一个字符 ##### 2、从根结点到某一节点，路径上经过的字符链接起来，为该节点对应的字符串 ##### 3、每个节点的子节点包含的字符都不相同 ##### 建树： ##### 儿子数组 son[][] 存储从节点 p 沿着 j 这条边走到的子节点 ##### 计数数组 cnt[] 存储以节点 p 结尾的单词的个数 ##### 节点编号 idx ##### 建树的逻辑： ##### 1.空Trie 仅有一个根节点，编号为 0，son[][] 初始值都为 0 ##### 2.从根开始插，枚举字符串的每个字符 ##### 如果有儿子，则 p 指针走到儿子 ##### 没有则先创建儿子，p 指针再走到儿子 ##### 3.在单词结束点记录插入次数 #### 查询： ##### 1.从根开始查询，扫描字符串 ##### 2.有元素 s[i], 则往下继续走, 能走到词尾，则返回插入次数 ##### 3.无元素 s[i]，直接返回 0 ### Σ（西格玛） ##### Σ表示对一系列元素的求和操作。该符号通常用于表示需要对某个集合中的元素进行累加的情况。 ##### 使用方式：Σ（表达式，变量，起始值，结束值）（表达式表示每次累加的具体操作，变量表示循环变量，起始值和结束值表示循环的范围） #### 代码实现Σ： ```cpp #include <bits/stdc++.h> using namespace std; int main(){ int n; long long num=0; cin>>n; for(int i=1;i<=n;i++){ num += i; } cout<<num; return 0; } ``` #### 大插曲： ##### 按位或：| ##### 按位与：& ##### 按位异或：^（也就是上面的那个） ### 10.分块 ##### 注：严格来说，分块是一种思想，不是数据结构 ##### 基本思想：通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。 ##### 分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。 ##### 分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息。 ### 11.莫队 ##### 核心就两个字： #### 暴力！（钟神说的） ##### 例：枚举m个数，把数一个一个插入进去，取出左端点和右端点，查某个数共出现了几次 ##### 画图的时候有点像滑动窗口，但是不是哈 ##### 如果上一个左端点位置小于下一个左端点位置，删除两个队左端点空缺的部分，否则，补上两个队左端点空缺的部分 ##### 右端点相反（小于补，大于删） ### 12.求逆序对 ##### 枚举n个数，求有多少个i,j能使a[i]>a[j]且i<j ###### 可以用分治做 ##### 给定l,r,找出[l,r]区间有多少个逆序对 ##### 二分找出中间数，分别算两边，找出i在左边，j在右边的答案 ##### 如果左边没数，放入右边 ##### 如果右边没数，放入左边（就是反着放） ## 还有 ### 全部数的区间——一定用分治！！！ ### 不要用endl!不要用endl!不要用endl!(重要的事说三遍)不然你就会变成苏畅（太慢了！