烟台五一培训day1笔记 最后更新于 2025-05-01 19:43:59

不完善的地方会补的 没写完啊啊 ## 程序相关 不要用`<<endl`！！！ 要用`"\n"`！！！ 注意不要把`\`打成`/` ## 栈&队列相关 ```cpp #include<queue> //#include<bits/stdc++.h> using namespace std; queue<int> q; //queue<队列里面的元素类型> 变量名; int main() { q.push(233); q.push(2233);//向队列里面加入一个元素 q.pop();//从队列中删除一个元素 删除是队列头的元素 233 void类型没有返回值 int x = q.front();//获取队列头元素 2233 cout << q.size() << endl;//获取队列剩余的元素个数 1 } ``` ### dfs&bfs实现 dfs用栈可以快速回溯（弹出栈头下一个就是） 但是容易爆栈（因为递归） bfs用队列实现即可 ### 单调队列 **让队列里的元素单调递增或递减** 如：1 2 3 4就是一个单调（递增）队列，注意1或2个数一定是单调队列 维护一个单调递增的队列：把不符合条件的删掉； 也就是说，一旦加入一个不是单调递增的数就删掉 举个例子：加入3 1 4 2 1. `3` 2. `3 1`删掉3 3. `1 4` 4. `1 4 2`删掉2 此时第四步的`[1,4]`就是单调队列 ### 双端队列 deque（stl） 但是不建议，因为用起来**时空都更差**，但方便，所以可以手写 特性：支持所有队列操作，两边都能进出 所以stl里的操作有好多种，前后查找和前后加入删除之类的 我们可以用deque来实现单调队列 一个while，持续判断队列是不是保持单调状态，如果不是就删掉队尾 或者说直到前面的数是再加入新数后符合单调条件再加入 维护单调队列：`4 2 5 7` 维护出来就是`[2,5,7]` 那问题来了，一段区间的最小值和单调队列有什么关系？ **最小值一定是单调队列的最前面！！ 因为最小值插进来之后，后面的数是不可能来到它前面的，它就是在最前面** ### 总结 总结一下，找一个区间的最小值，就是找出其单调队列维护完后的第一个数 **维护好双指针，就能保证每个数都加入和删除一次** 即为O（n）复杂度，每次操作是O（1） ### 例题 [P1886](https://www.luogu.com.cn/problem/P1886) 滑动窗口 模板题没有好说的 ## 堆 分为大根堆和小根堆 小根堆包括插入一个数、删除最大值、询问最大值 简单实现方法：stl queue->`priority_queue<int> q;` 这样我们就生成了一个大根堆 堆也是平衡树的基础，但手写大根堆好像并没什么用 大根堆的性质与栈类似 小根堆（最简单的）实现方法：把所有的元素存进去的时候取其相反数，其他操作也是 **取负号。** 问题来了，把结构体存到堆里怎么存？ 新的函数：重载运算符，会定义两个小于运算怎么去算 和“<”一样？包不是的 ，把 < 改为 > 就可以改算法 **但是不能重载大于号** 结论：把结构体放在stl比大小，**只能用小于号** 手写堆不用管（？） 可以用来实现二叉树（本质就是一颗二叉树） 二叉树指有右儿子就一定有左儿子，**即完全二叉树** 写法啊。 ```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 } ``` ## 附录（题目） ~~[A](https://www.luogu.com.cn/problem/P3378) 已过~~ ~~[B](https://www.luogu.com.cn/problem/P1886) 已过~~ [C](https://www.luogu.com.cn/problem/P3528) 未过 ~~[d](https://www.luogu.com.cn/problem/P3372) 已过~~ ~~[e](https://www.luogu.com.cn/problem/P3373) 已过~~ [f](https://www.luogu.com.cn/problem/P4113) 未过 [g](https://www.luogu.com.cn/problem/P9753) 未过 [h](https://www.luogu.com.cn/problem/P3367) 未过 ~~[i](https://www.luogu.com.cn/problem/P8306) 已过~~ [j](https://www.luogu.com.cn/problem/P10471) 未过