蓝桥杯算法竞赛必备模板

把原来 30 个模板里所有明显写错/易错点都修掉，并补齐了国一常用的关键细节（初始化、下标、常用接口）。

统一约定：数组默认 1..n（更贴竞赛习惯）；需要 0..n-1 的我会特别标注。

0. 通用头文件与常用定义（建议放最上面）

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

using ll = long long;
using PII = pair<int,int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

01. 快速排序（Hoare 划分，正确版）

void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l – 1, j = r + 1;
int x = q[(l + r) >> 1];

while (i < j)
{
do i++; while (q[i] < x);
do j–; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}

02. 二分查找（0..n-1，下标版）

int binary_search_idx(int a[], int n, int x)
{
int l = 0, r = n – 1;
while (l <= r)
{
int mid = l + (r – l) / 2;
if (a[mid] == x) return mid;
else if (a[mid] < x) l = mid + 1;
else r = mid – 1;
}
return -1;
}

国一更常用的是“二分边界”（lower_bound/upper_bound），但这版等值查找没问题。

03. 前缀和（1..n）

// a[1..n]
vector<ll> s(n + 1, 0);
for (int i = 1; i <= n; i++) s[i] = s[i – 1] + a[i];

auto query_sum = [&](int l, int r) -> ll {
return s[r] – s[l – 1];
};

04. 差分数组（区间加，1..n）

// b[1..n+1] 初始化为 0
void insert_range(vector<ll>& b, int l, int r, ll c)
{
b[l] += c;
b[r + 1] -= c;
}

// 恢复得到 a[1..n]
void build_from_diff(vector<ll>& a, vector<ll>& b, int n)
{
for (int i = 1; i <= n; i++)
{
b[i] += b[i – 1];
a[i] = b[i];
}
}

05. 双指针 / 滑动窗口（通用框架，0..n-1）

int res = 0;
for (int l = 0, r = 0; r < n; r++)
{
// 更新窗口信息：加入 a[r]
// …

while (l <= r && /*窗口不合法*/ false)
{
// 移除 a[l]
// …
l++;
}

res = max(res, r – l + 1);
}

06. 快速幂（正确参数：a^k mod p）

ll qmi(ll a, ll k, ll p)
{
ll res = 1 % p;
a %= p;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}

07. DFS（图遍历）

// g[1..n]
vector<vector<int>> g;
vector<int> st;

void dfs(int u)
{
st[u] = 1;
for (int v : g[u])
if (!st[v])
dfs(v);
}

08. BFS（图遍历）

void bfs(int start)
{
queue<int> q;
vector<int> st(g.size(), 0);
q.push(start);
st[start] = 1;

while (!q.empty())
{
int t = q.front(); q.pop();
for (int v : g[t])
{
if (!st[v])
{
st[v] = 1;
q.push(v);
}
}
}
}

09. 全排列（1..n）

int n;
vector<int> path;
vector<int> used;

void perm_dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i++) cout << path[i] << ' ';
cout << '\\n';
return;
}
for (int i = 1; i <= n; i++)
{
if (!used[i])
{
used[i] = 1;
path[u] = i;
perm_dfs(u + 1);
used[i] = 0;
}
}
}

10. 连通块（网格 DFS Flood Fill）

int n, m;
vector<string> grid;
vector<vector<int>> st2;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool valid(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#';
}

void dfs_grid(int x, int y)
{
st2[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny) && !st2[nx][ny])
dfs_grid(nx, ny);
}
}

11. BFS 最短路（无权图）

vector<int> bfs_shortest(int start)
{
int n = (int)g.size() – 1; // 若你用 1..n
vector<int> dist(n + 1, -1);
queue<int> q;

dist[start] = 0;
q.push(start);

while (!q.empty())
{
int t = q.front(); q.pop();
for (int v : g[t])
{
if (dist[v] == -1)
{
dist[v] = dist[t] + 1;
q.push(v);
}
}
}
return dist;
}

12. 并查集 DSU（路径压缩 + 按大小合并）

国一建议加上 size/rank，稳且快。

struct DSU
{
vector<int> p, sz;
DSU(int n = 0) { init(n); }

void init(int n)
{
p.resize(n + 1);
sz.assign(n + 1, 1);
iota(p.begin(), p.end(), 0);
}

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

bool unite(int a, int b)
{
a = find(a), b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};

13. Dijkstra（非负权，堆优化）

vector<vector<pair<int,int>>> wg; // (to, w)

vector<ll> dijkstra(int s)
{
int n = (int)wg.size() – 1; // 若 1..n
vector<ll> dist(n + 1, LINF);
vector<int> st(n + 1, 0);

priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> heap;
dist[s] = 0;
heap.push({0, s});

while (!heap.empty())
{
auto [d, ver] = heap.top();
heap.pop();
if (st[ver]) continue;
st[ver] = 1;

for (auto [v, w] : wg[ver])
{
if (dist[v] > d + w)
{
dist[v] = d + w;
heap.push({dist[v], v});
}
}
}
return dist;
}

14. 拓扑排序

vector<int> topo_sort(int n, vector<vector<int>>& g)
{
vector<int> indeg(n + 1, 0);
for (int u = 1; u <= n; u++)
for (int v : g[u])
indeg[v]++;

queue<int> q;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0) q.push(i);

vector<int> order;
while (!q.empty())
{
int t = q.front(); q.pop();
order.push_back(t);
for (int v : g[t])
{
if (–indeg[v] == 0)
q.push(v);
}
}
// 若 order.size() < n，说明有环
return order;
}

15. Kruskal（最小生成树）

struct Edge
{
int a, b, w;
bool operator<(const Edge& other) const { return w < other.w; }
};

ll kruskal(int n, vector<Edge>& edges)
{
sort(edges.begin(), edges.end());
DSU dsu(n);
ll res = 0;
int cnt = 0;

for (auto &e : edges)
{
if (dsu.unite(e.a, e.b))
{
res += e.w;
cnt++;
if (cnt == n – 1) break;
}
}
// 若 cnt < n-1，图不连通
return res;
}

16. Floyd（多源最短路）

// dist[1..n][1..n], 初始化：dist[i][i]=0, 有边 dist[u][v]=min(dist[u][v], w)
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

17. 二分图染色（判二分图：补齐冲突判断）

vector<int> color; // 0 未染色，1/2 两种颜色

bool bipartite_dfs(int u, int c)
{
color[u] = c;
for (int v : g[u])
{
if (!color[v])
{
if (!bipartite_dfs(v, 3 – c)) return false;
}
else if (color[v] == c) return false;
}
return true;
}

bool is_bipartite(int n)
{
color.assign(n + 1, 0);
for (int i = 1; i <= n; i++)
if (!color[i])
if (!bipartite_dfs(i, 1))
return false;
return true;
}

18. 01 背包（倒序）

// v[i], w[i], i=1..n, 容量 m
vector<ll> f(m + 1, 0);
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j–)
f[j] = max(f[j], f[j – v[i]] + w[i]);

19. 完全背包（正序）

vector<ll> f(m + 1, 0);
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j – v[i]] + w[i]);

20. 多重背包（朴素正确版）

vector<ll> f(m + 1, 0);
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= 0; j–)
{
for (int k = 1; k <= s[i] && k * v[i] <= j; k++)
f[j] = max(f[j], f[j – k * v[i]] + 1LL * k * w[i]);
}
}

国一建议：后续你再把它升级成“二进制拆分”版本（更常用不超时）。

21. LIS（O(n^2) 朴素版，正确）

vector<int> f(n + 1, 1);
for (int i = 1; i <= n; i++)
{
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);

22. LCS（二维 DP）

// a[1..n], b[1..m]
vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i] == b[j]) f[i][j] = f[i – 1][j – 1] + 1;
else f[i][j] = max(f[i – 1][j], f[i][j – 1]);
}
}

23. 区间 DP（按长度枚举，修正 r 与转移）

// 示例：f[l][r] = min over k (f[l][k] + f[k+1][r] + cost(l,k,r))
// 这里不给具体 cost，你自己按题填。
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len – 1 <= n; l++)
{
int r = l + len – 1;
f[l][r] = INF; // 或 LINF

for (int k = l; k < r; k++)
{
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] /* + cost */);
}
}
}

24. 状态压缩 DP（子集转移）

// n <= 20 常见
int N = 1 << n;
vector<ll> f(N, LINF);
f[0] = 0;

for (int s = 1; s < N; s++)
{
for (int i = 0; i < n; i++)
{
if (s >> i & 1)
{
f[s] = min(f[s], f[s ^ (1 << i)] + cost[i]);
}
}
}

25. 单调栈（找左侧第一个更小）

stack<int> st;
for (int i = 1; i <= n; i++)
{
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
// 此时 st.top() 就是 i 左侧第一个 < a[i] 的位置（若存在）
st.push(i);
}

26. 单调队列（滑动窗口最大值，完整正确版）

deque<int> q; // 存下标，保证 a[q] 单调递减
for (int i = 1; i <= n; i++)
{
while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
q.push_back(i);

// 窗口长度为 k，移除过期元素（i-k 之前的）
while (!q.empty() && q.front() <= i – k) q.pop_front();

if (i >= k)
{
int mx = a[q.front()];
// 使用 mx
}
}

27. 树状数组 BIT

struct BIT
{
int n;
vector<ll> tr;
BIT(int n=0){ init(n); }
void init(int n_)
{
n = n_;
tr.assign(n + 1, 0);
}
static int lowbit(int x){ return x & -x; }

void add(int x, ll c)
{
for (int i = x; i <= n; i += lowbit(i))
tr[i] += c;
}

ll sum(int x)
{
ll res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}

ll range_sum(int l, int r)
{
return sum(r) – sum(l – 1);
}
};

28. 线段树 build（区间和版，统一结构体）

struct Node
{
int l, r;
ll sum;
};

vector<Node> tr; // 4*n
vector<ll> a; // 1..n

void pushup(int u)
{
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void build(int u, int l, int r)
{
tr[u] = {l, r, 0};
if (l == r)
{
tr[u].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(u<<1, l, mid);
build(u<<1|1, mid + 1, r);
pushup(u);
}

29. 线段树 query（区间和）

ll query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

int mid = (tr[u].l + tr[u].r) >> 1;
ll res = 0;

if (l <= mid) res += query(u<<1, l, r);
if (r > mid) res += query(u<<1|1, l, r);

return res;
}

30. KMP（next + 匹配，完整正确版，1-index）

// p[1..m], s[1..n]
vector<int> ne(m + 1, 0);

// 1) 求 next
for (int i = 2, j = 0; i <= m; i++)
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}

// 2) 匹配：返回所有匹配起点（1-index）
vector<int> pos;
for (int i = 1, j = 0; i <= n; i++)
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j++;
if (j == m)
{
pos.push_back(i – m + 1);
j = ne[j];
}
}

现在这份“模板库”已经能覆盖蓝桥绝大多数题

如果你接下来继续冲国一，最值得再加的（按性价比排序）：