CSP认证练习题目推荐 （1）

主要是几道比较经典的题目，如果是奔着200分，不知道该怎么备考，可以跟着博主一起准备(博主学校毕业要求)。缺漏在所难免，各位如果有更好的题目推荐可以发到评论区。

官网模拟系统网址
不过这个需要认证考试的准考证，才能解锁一次模拟机会。可以去Acwing上找免费的真题(但可能最新的题目不全)。

DFS+剪枝（分支界限），BFS以及记忆化搜索

通用 DFS 模板

void dfs(状态参数...) {
    // 1. 递归边界：到达终点条件
    if (满足结束条件) {
        处理结果; // 比如计数、输出路径
        return;
    }

    // 2. 枚举选择
    for (每一个可能的选择) {
        if (选择合法) {
            做选择;      // 更新状态
            dfs(更新后的状态);
            撤销选择;    // 回溯（如果需要）
        }
    }
}

八皇后问题

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, cnt = 0;
int pos[100];
// 记录位置，索引为行，值为列
bool col[100], dg[100], udg[100];
void dfs(int row){
    // 中止条件，row = n，说明已经全部走完，找到一个解
    if(row == n + 1){
        cnt++; //记数解的个数
        if(cnt <= 3){
            for(int i = 1; i <= n; i++){
                cout << pos[i] << (n == i ? '\n' : ' '); 
            }
        }
        return;
    }
    for(int i = 1; i <= n ;i++){ // 判断在row行，col列是否放皇后
        if(!col[i] && !dg[row - i + n] && !udg[row + i]){ // 如果不冲突，放皇后
            col[i] = dg[row - i + n] = udg[row + i] = true; // 表示当前位置已被皇后占用
            pos[row] = i;
            dfs(row + 1); //递归找下一行的皇后
            col[i] = dg[row - i + n] = udg[row + i] = false;
        }
    }

    
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    dfs(1);
    cout << cnt;
    return 0;
}

求先序遍历

#include<bits/stdc++.h>
using namespace std;
string inOrder, postOrder;
// 结果为求先序遍历，参数分别为中序遍历区间、后序遍历区间
void dfs(int inL, int inR, int postL, int postR){
    // 先找结束条件
    if(inL > inR || postL > postR) return;
    // 拆分子问题，找树根，划分中序遍历。
    int root = inOrder.find(postOrder[postR]);
    cout << postOrder[postR];
    // 根据树根划分左右子树的范围
    int leftSize = root - inL; //左子树的规模，自然可以算出右子树的范围
    // 对左右子树分别找先序遍历
    //左子树
    dfs(inL, root - 1, postL, postL + leftSize - 1);
    // 右子树
    dfs(root + 1, inR, postL + leftSize, postR - 1);
    
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> inOrder >> postOrder;
    dfs(0, inOrder.size() - 1, 0, postOrder.size() - 1);
    
    return 0;
}

数的划分

#include<bits/stdc++.h>
using namespace std;
int n, k, ans; //整数n 份数 计数答案
void dfs(int l, int cur, int s){ // 当前分配里最小的份数 当前份数 当前所有份数的整数和 
    if(cur == k + 1){
        if(s == n) ans++;
        return;
    }
    // s+i<=n，确保再加上这一份不会超过n
    for(int i = l; s + i <= n; i++) dfs(i, cur + 1, s + i); 

}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}

BFS

马的遍历

#include<bits/stdc++.h>
using namespace std;
const int N = 401;
int n, m;
int dest[N][N]; // 存放每个位置访问次数
int dx[8] = {-1, -1, -2, -2, 1, 1, 2, 2}; // 日字形对索引的移动
int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
void bfs(int ox, int oy){ // old横坐标
    queue<pair<int, int>> q;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            dest[i][j] = -1; //初始化位置访问次数为-1
        }
    }
    q.push({ox, oy}); // 当前位置放入队列
    dest[ox][oy] = 0; // 置为0，表示有可达可能
    while(!q.empty()){ // 如果队列不为空，尝试跳到八个点
        int x = q.front().first; // 取出队列首部的坐标，表示每次跳到的位置
        int y = q.front().second;
        q.pop(); // 先进先出，取到当前位置就删掉 
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i]; // 可能跳到的新位置
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue; //如果新位置超出了棋盘
            if(dest[nx][ny] != -1) continue; // 如果新位置不是-1，说明当前位置已经找到过最短路径了，再访问只会得到更长的路径
            dest[nx][ny] = dest[x][y] + 1; // 如果新位置在棋盘上，按老的xy加1
            q.push({nx, ny}); //把新的位置插入queue，表示要在新位置再跳
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << dest[i][j] << " ";
        }
        cout << endl;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int x, y;
    cin >> n >> m >> x >> y;
    bfs(x - 1, y - 1);
    
    return 0;
}

机器人复健指南

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

const int N = 101;
int dest[N][N]; // 记录每个格子到起点的步数，-1表示未访问
int n, k, x, y;
int dx[8] = {1,2,1,2,-1,-2,-1,-2};
int dy[8] = {2,1,-2,-1,2,1,-2,-1};

void bfs(int ox, int oy){
    // 初始化
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            dest[i][j] = -1;

    queue<pair<int,int>> q;
    q.push({ox, oy});
    dest[ox][oy] = 0; // 起点步数为0

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if(dest[x][y] == k) continue; // 已经达到最多步数，不再扩展

        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 边界检查
            if(dest[nx][ny] != -1) continue; // 已访问过
            dest[nx][ny] = dest[x][y] + 1; // 更新步数
            q.push({nx, ny}); // 加入队列继续扩展
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> x >> y;

    bfs(x - 1, y - 1); // 转成0-based索引

    int ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(dest[i][j] != -1) ans++; // 统计能到达的格子数

    cout << ans << "\n";
    return 0;
}

如果这篇文章对你有帮助，请点赞、评论、收藏，创作不易，你的支持是我创作的动力。