OI 模板合集

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

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

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;
    }
}

#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;
}

#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;
}

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

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

// 使用队列（伪代码）
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; // 必须在此处标记，避免某节点多次入队
            }
        }
    }
}

#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;    
}

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

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

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

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

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

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