CSP试题库典型示例解析(附代码模板)

CSP认证的题目类型相对固定，很多同学刷了大量题目却抓不住规律。今天精选几道典型例题，帮大家摸清套路，做到举一反三。

📖 一、基础语法类

典型题：输入输出格式处理

这类题看似简单，但每年都有人因为空格、回车、换行处理不当丢分。

例：输入包含多组数据，以0 0结束，求和。

while (cin >> a >> b) {
    if (a == 0 && b == 0) break;
    cout << a + b << endl;
}

关键点：看清楚输入范围、终止条件、输出格式（是否有空格），这些细节决定你是否AC。

🔢 二、数论类

典型题：质数判断、最大公约数

CSP初赛和复赛都常考数论，核心是理解辗转相除法和质数的性质。

例：判断一个数是否为质数（常见优化版本）。

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

关键点：质数判断不必遍历到n，只需到√n，这是O(√n)复杂度，比O(n)快很多。

📊 三、动态规划（DP）

典型题：最长上升子序列（LIS）

DP是CSP最难的部分，但LIS是相对好理解的入门题。

例：给定序列，求最长上升子序列长度。

// O(n²) 版本
int lis = 0;
for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
        if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
    }
    lis = max(lis, dp[i]);
}

// O(n log n) 优化版本（推荐掌握）
vector tail;
for (int x : a) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) tail.push_back(x);
    else *it = x;
}
int lis = tail.size();

关键点：LIS两种写法都要会，O(n log n)版本用二分查找优化，是高频考点。

🌳 四、图论基础

典型题：图的遍历与连通性

BFS/DFS是图论的基础，也是CSP常考内容。

例：判断无向图是否连通。

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

// 主逻辑：统计连通块数量
int components = 0;
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i);
        components++;
    }
}
cout << (components == 1 ? "YES" : "NO") << endl;

关键点：理解DFS/BFS的适用场景：DFS适合路径搜索，BFS适合最短路。要能根据题目要求选择合适的遍历方式。

🔤 五、字符串处理

典型题：字符串匹配与处理

例：统计字符串中各字符出现次数。

int cnt[256] = {0};
string s;
cin >> s;
for (char c : s) {
    cnt[(int)c]++;
}
for (int i = 0; i < 256; i++) {
    if (cnt[i] > 0) {
        cout << (char)i << ": " << cnt[i] << endl;
    }
}

关键点：字符串题常用数组做计数（哈希思想），空间换时间。注意ASCII字符范围是0-127或0-255。

💡 刷题建议

1. 先理解思路，再自己写代码
看题解懂了不等于会做，一定要自己敲一遍，跑通样例。

2. 分类刷题，不要乱序
按类型集中练习：这一周专攻DP，下一周专攻图论，系统性更强。

3. 重视样例和边界条件
CSP题目分步给分，边界情况处理正确也能拿部分分。

4. 不会的题先放一放，再回来做
卡太久会打击信心，隔一段时间再看可能就通了。