清北学堂五一集训Day 1

# 前言：
$2025.5.1$ $18:22$ 建议先看后记
## 免责声明
该文章中大部分代码为神犇 $zhx$ 亲自创作，本人仅做搬运与借鉴
# 重点（ $zhx$ 语录）
 >1.如果题目给了N个数，且这些数的顺序对答案**没有影响**，那么先排序再说——钟皓曦

>2.不要用`endl`——钟皓曦

![](https://cdn.luogu.com.cn/upload/image_hosting/3rvduqng.png)  
图：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)
![](https://cdn.luogu.com.cn/upload/image_hosting/swzlg1vp.png)
# 后记
$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$ 语录一句

正在渲染内容...