OI 模板合集

此处存放本蒟蒻写过的各种 cpp 模板，不喜勿喷~

# 目录
- 基本算法
- 前缀和
- 差分
- 二分答案
- 基本数据结构
- 栈
- 队列
- 搜索
- 图上深度优先遍历
- 图上广度优先遍历

# 基本算法

## 前缀和

```cpp
for (int i = 1; i <= n; i ++) {
cin >> arr[i];
sum[i] = sum[i - 1] + arr[i];
}
```

## 差分

```cpp
for (int i = 1; i <= n; i ++) {
cin >> arr[i];
dif[i] = arr[i] - arr[i - 1];
}
```

## 二分答案

```cpp
int l = 0, r = 1e9, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
```

# 基本数据结构

## 栈

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
int T;
cin >> T;
while (T--) {
vector<unsigned long long> st;
int n = 0;
cin >> n;
for (int i = 1; i <= n; i ++) {
string op;
unsigned long long x;
cin >> op;
if (op == "push") {
cin >> x;
st.push_back(x);
} else if (op == "query") {
if (st.size() != 0) {
cout << st.back() << endl;
} else {
cout << "Anguei!" << endl;
}
} else if (op == "size") {
cout << st.size() << endl;
} else if (op == "pop") {
if (st.size() != 0) {
st.pop_back();
} else {
cout << "Empty" << endl;
}
}
}
}
return 0;
}
```

## 队列

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
int N = 0;
cin >> N;
queue <int> q;
while (N--) {
int op = 0;
cin >> op;

if (op == 1) {
int x = 0;
cin >> x;
q.push(x);
} else if (op == 2) {
if (q.size() == 0) {
cout << "ERR_CANNOT_POP" << endl;
} else {
q.pop();
}
} else if (op == 3) {
if (q.size() == 0) {
cout << "ERR_CANNOT_QUERY" << endl;
} else {
cout << q.front() << endl;
}
} else {
cout << q.size() << endl;
}
}
return 0;
}
```

# 搜索

## 深度优先搜索

```cpp
// 暴力枚举所有方案（伪代码）
void dfs(int n, ...) {
if (所有状态均枚举完成) {
...
return; // 一定要返回
}
for (遍历当前状态所有扩展可能性) {
if (判断扩展状态是否合法) {
调整状态
dfs(n + 1, ...); // 向深层递归搜索
复原状态（一定要回溯！！）
}
}
}
```

## 图上深度优先遍历

```cpp
// 用 vis 数组跳过已经走过的点（伪代码）
void dfs(int u) { // 当前的位置（节点）
vis[u] = 1;
for (与 u 相邻的节点 v) {
if (!vis[v]) dfs(v);
}
}
dfs(s); // 从起点开始
```

## 图上广度优先遍历

```cpp
// 使用队列（伪代码）
void bfs() {
queue<T> q;
q.push(s); // 起点入队
vis[s] = 1;
while (!q.empty()) {
T u = q.front();
q.pop();
for (与 u 相邻的节点 v) {
if (!vis[v]) {
q.push(v);
vis[v] = 1; // 必须在此处标记，避免某节点多次入队
}
}
}
}
```

## bfs 走迷宫

```cpp
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}

struct node {
int x, y, d;
node(int xx, int yy, int dd) { // 构造函数
x = xx;
y = yy;
d = dd;
}
};

int bfs(int sx, int sy) {
queue<node> q;
q.push(node(sx, sy, 0));
vis[sx][sy] = true;
while (!q.empty()) {
node now = q.front();
q.pop();
for (int i = 0; i < 4; i ++) {
int tx = now.x + dir[i][0];
int ty = now.y + dir[i][1];
if (in(tx, ty) and maze[tx][ty] != '*' and !vis[tx][ty]) {
if (maze[tx][ty] == 'T') {
return now.d + 1;
} else {
vis[tx][ty] = true;
q.push(node(tx, ty, now.d + 1));
}
}
}
}
return -1;
}

int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> maze[i];
}
int x, y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') {
x = i, y = j;
}
}
}

cout << bfs(x, y) << endl;
return 0;
}
```

## 双向 bfs

```cpp
// （伪代码）
将 起始状态 和 目标结点 入队

标记起始结点为 1
标记目标结点为 2

while(队列不为空)
{
从队首扩展出新个结点

如果 新扩展出的结点已经被其他数字标记过，表示已经搜索到了一种方案，算法结束。

如果新个结点是从起始状态扩展来的，那么将这个该结点标记 1 并入队

如果新个结点是从目标结点扩展来的，那么将这个该结点标记 2 并入队
}
```

# 数据结构进阶

# 动态规划