清北学堂五一集训Day 1 最后更新于 2025-05-02 13:54:42

# 前言： $2025.5.1$ $18:22$ 建议先看后记 ## 免责声明 该文章中大部分代码为神犇 $zhx$ 亲自创作，本人仅做搬运与借鉴 # 重点（ $zhx$ 语录） >1.如果题目给了N个数，且这些数的顺序对答案**没有影响**，那么先排序再说——钟皓曦 >2.不要用`endl`——钟皓曦  图：zhx大佬现场测试输出一千万组数据的用时 本文链接中的`endl`为zhx大佬的~~独特写法~~ >3.CCF的出题人从不看考纲，而CCF的考纲却因出题人年年更新——钟皓曦 >4.在c++中，数据结构占 $50\%$,算法占剩下 $50\%$——钟皓曦 >5.有测试点（OI制）的题目自己调——钟皓曦 # 上午： ## 第一节课 ### [队列](https://www.luogu.com.cn/article/7a6sb82y)（ $queue$ ） 特点：先进先出(**f**$irst$ **i**$n$ **f**$irst$ **o**$ut$ 简称 $FIFO$) 1.`q.push(x)` 将元素x加入队列 2.`q.pop()` 将队首元素删除队列 3.`q.front()` 输出**队首**元素 4.`q.size()` 输出队列剩余元素个数 ### 手写队列（结构体 $struct$ 模拟） ### [栈](https://www.luogu.com.cn/article/ub1cvqix)（ $stack$ ） 特点：先进后出(**f**$irst$ **i**$n$ **l**$ast$ **o**$ut$ 简称 $FILO$) [$P3378$](https://www.luogu.com.cn/problem/P3378)（板子） [手写栈（$P3378$ 正解）](https://www.luogu.com.cn/record/206738277) #### 左移右移 1.常用位运算 $x << 1 = x \times 2$ $x >> 1 = x \div 2$ 2.乘方（由1.中的特殊到现在的一般） $x << y = x \times 2 ^ y$ $x >> y = x \div 2 ^ y$ 1.`s.push(x)` 将元素x加入栈 2.`s.pop()` 删除栈顶元素 3.`s.top()` 输出**栈顶**元素 4.`s.size()` 输出栈剩余元素个数 ### [双端队列](https://www.luogu.com.cn/article/80fva93d)（ $deque$ ） 1.`q.push_front()` 从前面加入 2.`q.pop_front()` 从前面删除 3.`q.front()` 询问前面的数是多少 4.`q.push_back()` 从后面加入 5.`q.pop_back()` 从后面删除 6.`q.back()` 询问后面的数是多少 ## 第二节课 ### 堆（优先队列 $priority\_queue$ ） #### 大根堆 `priority_queue<int> q ;` #### 小根堆 `priority_queue<int,vector<int>,greater<int> > q;` -----------------------------------------------------^----- ------------------------------------------此处一定要有空格 最简单的实现方法就是在大根堆里存相应数的相反数 ```cpp q.push(-233);//注意负号 q.push(-2233);//注意负号 q.pop(); int x = -q.top();//注意负号 cout << q.size() << "\n"; ``` ### 重载运算符（堆的数据类型是结构体定义） 只能重载**小于号$<$** ```cpp struct node { int a , b ; }; bool operater<(const node &x,const node &y) { return x.a + x.b > y.a + y.b ; } ``` ### 手写[堆](https://www.luogu.com.cn/article/byf2tqbj) 本质：二叉树 堆的性质：有右儿子就一定有左儿子，即**完全二叉树** 关系： 父亲：$floor(i/2)$ 左儿子：$2i$ 右儿子：$2i+1$ ### 并查集 [$P3367$](https://www.luogu.com.cn/problem/P3367) [并查集模板（$P3367$ 正解）](https://www.luogu.com.cn/article/igc5m7uk) # 下午： ## 第一节课 #### [字典树 $trie$](https://www.luogu.com.cn/article/shppba2x) ## 第二节课 #### [分块](https://www.luogu.com.cn/article/hj4k1h0u) #### [莫队](https://www.luogu.com.cn/article/cd712gcq) ## 第三节课 #### [逆序对](https://www.luogu.com.cn/article/51o7rxn5)  # 后记 $2025.5.1$ $18:22$ 添加对应网址的`.me`版本： [队列](https://www.luogu.me/article/7a6sb82y) [栈](https://www.luogu.me/article/ub1cvqix) [双端队列](https://www.luogu.me/article/80fva93d) [堆](https://www.luogu.me/article/byf2tqbj) [字典树 $trie$](https://www.luogu.me/article/shppba2x) [分块](https://www.luogu.me/article/hj4k1h0u) [莫队](https://www.luogu.me/article/cd712gcq) [逆序对](https://www.luogu.me/article/51o7rxn5) $2025.5.1$ $19:47$ 应老师要求，今日题单完成如下： | 题号 | 完成情况 | | -----------: | -----------: | | $P3378$ | $true$ | | $P1886$ | $true$ | | $P3528$ | $true$ | | $P3372$ | $true$ | | $P3373$ | $true$ | | $P4113$ | $true$ | | $P9753$ | $false$ | | $P3367$ | $false$ | | $bzoj-P2054$ | $false$ | | $P8306$ | $false$ | | $P10471$ | $false$ | $2025.5.2$ $8:11$ 增加了小根堆的解释；补充了并查集的部分内容 $2025.5.2$ $13:26$ 补充 $zhx$ 语录一句