算法竞赛 · 从零到精通（第 8–13 讲）

第 8 讲 · 广度优先搜索（BFS）与网格图

BFS 与 DFS 的区别：DFS 是"一条路走到黑"，BFS 是"一层一层扩"。求最短步数一律优先想 BFS。

struct Node{ int x, y, d; }; // 坐标 + 步数
int bfs(int sx, int sy, int tx, int ty) {
    queue<Node> q;
    q.push({sx, sy, 0}); vis[sx][sy] = true;
    while (!q.empty()) {
        Node u = q.front(); q.pop();
        if (u.x == tx && u.y == ty) return u.d;
        for (int k = 0; k < 4; k++) {
            int nx = u.x + dx[k], ny = u.y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
                vis[nx][ny] = true;
                q.push({nx, ny, u.d + 1});
            }
        }
    }
    return -1;
}

第 9 讲 · 贪心：先拿容易的分

两种招牌套路

• 排序贪心：按某个关键字排序后依次取。典型：活动安排（结束越早越先选）、最少硬币（面额整除时）。
• 堆贪心：动态取当前最优，用 priority_queue 维护。典型：合并果子、任务调度。

// 活动安排：最多能参加几个活动
struct A{ int s, e; };
bool cmp(const A&a, const A&b){ return a.e < b.e; } // 按结束时间排序
int cnt = 0, last = -1;
for (auto &x : a)
    if (x.s >= last) { cnt++; last = x.e; }
cout << cnt << endl;

贪心最大的坑是"局部最优 ≠ 全局最优"（例如普通硬币找零）。写之前想一个反例；举不出反例再提交。

第 10 讲 · 动态规划入门：从斐波那契到背包

DP 四步法

• 一、 定义状态 dp[...] 表示什么（用一句话说清楚）
• 二、 找转移：当前状态由哪些更小的状态推来
• 三、 定初值：最小规模时答案是多少
• 四、 定顺序：从小到大保证"用的都先算好了"

// 0-1 背包：容量 V，n 件物品，取或不取，价值最大
int dp[1005] = {0};
for (int i = 1; i <= n; i++)
    for (int v = V; v >= w[i]; v--)   // 逆序！保证每件只用一次
        dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
cout << dp[V] << endl;

第 11 讲 · 图论入门：存图、遍历与最短路

// 邻接表
vector<int> g[100005];      // g[u] 存 u 的所有邻居
g[u].push_back(v); g[v].push_back(u); // 无向边
// 带权：vector<pair<int,int>> g[]; 存 (邻居, 边权)

• 无权图最短路 = BFS（原样跑第 8 讲代码）。
• 非负边权最短路 = 小根堆优化的 Dijkstra：每次弹出"当前离起点最近"的点松弛邻居。

// Dijkstra 核心（堆优化）
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
dis[s] = 0; pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dis[u]) continue;
    for (auto [v, w] : g[u])
        if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; pq.push({dis[v], v}); }
}

第 12 讲 · 并查集与最小生成树

// 并查集（路径压缩）——控制"谁和谁是一伙的"
int fa[100005];
int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int a, int b){ fa[find(a)] = find(b); }
// 初始化：for (int i = 1; i <= n; i++) fa[i] = i;
// 判环：若 find(u) == find(v) 说明 u、v 已经连通，再加边就成环

Kruskal 最小生成树（把 n 个点最少花费连起来）

1. 把所有边按边权从小到大排序；
2. 依次考虑每条边：两端点还不连通（并查集判断）就选它，否则跳过；
3. 选满 n−1 条边即完成。

第 13 讲 · 刷题路线图：接下来半年怎么练

• 第 1–2 周：CF 800 分题每天 3 道，只做"会做但写得慢"的题，练手感。
• 第 3–6 周：转 900–1100 分，开始计时（每道 30 分钟）；跟不上就回上一档。
• 第 2–3 个月：1100–1300 + 每周一场 Div.4/Div.3 比赛（打完必复盘错题）。
• 第 4–6 个月：1300–1600 + 开始碰"数据结构专题"（线段树、树状数组入门）。
• 参加比赛：CF 每周都有；校内赛/省赛按通知参加。比赛是最好的老师。

卡住了怎么办（重要）

• 一道题盯 40 分钟没思路 → 看题解（CF 每道题下方有 tutorial），看懂后关掉题解自己重写一遍。
• 写出来 WA → 自己造 5 组数据对拍（写个暴力程序互相对答案）。
• 还不行 → 到本站题库索引搜同类标签，做 3 道相似题找共性。