CSP真题解析第2期

📚 CSP第二轮认证冲刺必看！

一、前言

在CSP第二轮认证中，图论、动态规划和搜索是三大高频考点。本文选取2023-2024年度典型题目，从审题分析到代码实现进行完整讲解。

二、图论专题：最短路变形

【例题】灾后重建

题目简述：N个村庄之间有M条道路，每个村庄有一个修复时间t。求在任意时刻，两个指定村庄之间的最短通路。

解题思路

这是一道Dijkstra算法的变形题。关键在于：

1. 对每个节点的可用时间进行限制
2. 使用优先队列优化
3. 记录访问状态
4. 代码模板（C++）

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

struct Node {
    int v, w, time;
    bool operator<(const Node& other) const {
        return w > other.w;
    }
};

vector<vector<pair<int,int>>> g;
vector<int> repairTime;

vector<int> dijkstra(int n, int start, int limitTime) {
    vector<int> dist(n+1, INT_MAX);
    vector<bool> visited(n+1, false);
    priority_queue<Node> pq;

    dist[start] = 0;
    pq.push({start, 0, 0});

    while (!pq.empty()) {
        auto [u, d, t] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        if (t > limitTime) continue;

        visited[u] = true;

        for (auto [v, w] : g[u]) {
            int newTime = t + repairTime[v];
            if (newTime <= limitTime && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v], newTime});
            }
        }
    }
    return dist;
}

三、动态规划专题：状态压缩DP

【例题】铺砖问题

题目简述：用2×1的砖块铺满n×m的棋盘，求方案数。

代码模板

int dp[20][1<<12];
int n, m;

int dfs(int row, int state) {
    if (row == n) return state == 0 ? 1 : 0;
    if (dp[row][state] != -1) return dp[row][state];

    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (!(state & (1<<i))) {
            // 可以竖放
            if (i + 1 < m && !(state & (1<<(i+1)))) {
                ans += dfs(row, state | (1<<i) | (1<<(i+1)));
            }
            // 横放或跳过
            ans += dfs(row, state | (1<<i));
            break;
        }
    }
    return dp[row][state] = ans;
}

四、搜索专题：双向BFS

【核心模板】

int bidirectional_bfs(string start, string target) {
    if (start == target) return 0;

    unordered_set<string> front = {start};
    unordered_set<string> back = {target};

    int steps = 0;
    while (!front.empty() && !back.empty()) {
        if (front.size() > back.size())
            swap(front, back);

        unordered_set<string> next;
        for (auto& s : front) {
            for (auto& ns : getNeighbors(s)) {
                if (back.count(ns))
                    return steps + 1;
                if (!visited.count(ns)) {
                    visited.insert(ns);
                    next.insert(ns);
                }
            }
        }
        front = next;
        steps++;
    }
    return -1;
}

五、备考建议

1. 模板熟记：上述代码需要能够手写出来
2. 复杂度分析：每道题都要能分析时间和空间复杂度
3. 边界处理：注意n=1、m=1等边界情况
4. 多组数据：读入多组测试数据时要重置全局变量

六、往期回顾

👉 CSP试题库典型示例解析（1）

📌 关注公众号，回复"模板"获取更多代码模板资料