一些板子

**本博客由[@Nihachu](https://www.luogu.com.cn/user/1109610#main)的博客~~抄袭~~搬运而来**

(绝大部分代码来自[@Nihachu的博客](https://www.luogu.com.cn/blog/Nihachu-33/mu-ban-ji-he)~~若有侵权，就算联系我也不会删除~~）

一、二叉树相关：

1、深度优先：

前序遍历(根，左子树，右子树)

```cpp
void dfs(int x){
printf("%d\n",x);
if(ls[x]) dfs(ls[x]);
if(rs[x]) dfs(rs[x]);
}

```

中序遍历（左子树，根，右子树）

```cpp
void dfs(int x){
if(ls[x]) dfs(ls[x]);
printf("%d\n",x);
if(rs[x]) dfs(rs[x]);
}
```

后序遍历（左子树，右子树，根）

```cpp
void dfs(int x){
if(ls[x]) dfs(ls[x]);
if(rs[x]) dfs(rs[x]);
printf("%d\n",x);
}
```

2、广度优先：

层次遍历（从上到下，从左到右依次输出同一层的节点）：

```cpp
void bfs(int x){
q[++top] = x;
for(int i = 1; i <= top; i ++){
int now = q[i];
printf("%d\n",now);
if(ls[now]) q[++top] = ls[now];
if(rs[now]) q[++top] = rs[now];
}
}
```

二、动态规划相关：

1、01背包（已降维）

```cpp
for(int i = 1; i <= n; i ++){
for(int j = m; i >= w[i]; j --){
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
}
}
```

2、完全背包
```cpp
for(int i = 1; i <= n; i ++){
for(int j = w[i]; i <= m; j ++){
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
}
}
```
3、背包计数
```cpp
for(int i = 1; i <= n; i ++){
for(int j = m; i >= w[i]; j --){
dp[j] += dp[j - w[i]];
}
}
```
（若要求恰好为m，则dp[0]初始化为1，其他均为0）；

4、二进制拆分（用于多重背包）
```cpp
for(int i = 1; i <= n1; i ++){
scanf("%d %d %d",&a, &b, &c);
for(int k = 1; k <= c; k <<= 1){
v[++u] = k * a; w[u] = k * b;
c -= k;
}
if(c) v[++u] = a * c,w[u] = b * c;
}
```
三、卡时间相关

1、快读
```cpp
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
```
2、快写
```cpp
void write(int x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
```
3、手动o2优化
```cpp
#pragma GCC optimize(2)
```
四、并查集

1、查询 + 路径压缩
```cpp
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
```
2、合并x，y所属集合
```cpp
void marge(int x, int y){
int u = find(x), v = find(y);
if(u == v) return;
fa[u] = v;
}
```
3、合并x， y 所属集合（按秩合并）
```cpp
void marge(int x, int y){
int u = find(x), v = find(y);
if(u == v) return;
if(rk[u] > rk[v]) swap(u,v); // 把深度小的合并到深度大的上面；
fa[u] = v;
rk[v] += rk[u] == rk[v]; //如果同级，则合并后深度加一，否则不变；
}
```
五、单调队列
```cpp
//n为数据个数，m为窗口长度；
for(int i = 1; i <= n; i ++){
if(q[head] <= i - m) head ++;
while(head <= tail && a[q[tail]] < a[i]) tail --;
q[++tail] = i;
ans[i] = a[q[head]];
}
for(int i = m ; i <= n ; i ++){
//对每个窗口中已选出的数据进行处理 ；
}
```
六、图论

1、链式前向星
```cpp
void add(int x, int y){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
```
2、图的dfs遍历（以链式前向星为例）
```cpp
void dfs(int x) {
vis[x] = 1;//状态更新为已访问
printf("%d ",x);//输出
for(int i = head[x];i;i = nxt[i])//找到所有x能到达的点与x之间的边的编号
if(!vis[to[i]]) {//如果该点未访问过
dfs(to[i]);//访问该点
}
```
3、tarjan求scc（强连通分量）
```cpp
/*
timestamp：时间戳
scccnt：当前强连通分量编号
sccid[u]：编号为u的节点所在的强连通分量的编号
stk:栈
top:栈顶
in[u]:编号为u的节点是否在栈内
sccsize[u]编号为u的节点所在的强连通分量的大小
*/
void tarjan(int u) {
low[u] = dfn[u] = ++timestamp;
in[u] = 1;
stk[++top] = u;
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(in[v]) low[u] = min(low[u],dfn[v]);
if(low[u] == dfn[u]) {
scccnt++;
while(stk[top] != u) {
sccid[stk[top]] = scccnt;
in[stk[top]] = 0;
sccsize[scccnt]++;
top--;
}
sccid[stk[top]] = scccnt;
in[stk[top]] = 0;
sccsize[scccnt]++;
top--;
}
}
}
```
七、数据结构

1、树状数组

2、线段树