2025五一集训营（普转提）Day1上午笔记 最后更新于 2025-05-01 16:33:06

# 数据结构 ### 队列&栈 ~~太简单了~~ ###### 创建栈：stack<数据类型> 变量名 ###### 创建队列：queue<数据类型> 变量名 ###### 常用指令：push,pop,size,front（后面一定要加()，char类型push()里要加插入的东西） ### 单调队列 ###### 也就是滑动窗口，[模板传送门](https://www.luogu.com.cn/problem/P1886) ###### ~~我也不会讲啊，自行看题解吧~~ ### 单调栈 ###### 钟神说了这玩意纯fw，就不说了，[模板传送门](https://www.luogu.com.cn/problem/P5788) ### 堆 ###### 和队列&栈差不多，分为大根堆和小根堆 ###### 创建堆：priority_queue<数据类型> 变量名 ###### 大根堆：常用，取最大值 ###### 小根堆：由大根堆转，有两种方法 #### 方法一： ###### 直接在插入值前加负号 #### 方法二： ###### 创建堆代码中的<数据类型>改为<数据类型，vector<数据类型>,greater<数据类型> >即可 ### 手写堆 ###### ~~问为什么不讲手写栈和手写队列，因为都差不多~~ ###### 和二叉树差不多 ###### 如果有右儿子，就一定有左儿子 ###### 插入一个数到末尾，如果这个数比它的父亲大，那么交换（swap） ###### 时间复杂度：O(logn) ### 左移右移位运算 ###### 稍稍插入一点位运算的东西 ##### $x>>y==x/2^y$ ##### $x<<y == x*2^y$ ### 并查集 ###### 所谓并查集，即是合并集合&查询集合中的值，简称并查集 ###### 先把每个东西的箭头指向自身 ###### 从某个点出发，看最后会走到哪里 ###### 合并：赋值一个集合=另一个集合 ###### 查询：查询某个值是否在某个集合 #### 核心代码（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)