提高组 CSP-S 2026 初赛模拟卷 7

#include <iostream>
using namespace std;

unsigned short tot;

void Hanoi(int n, char A, char B, char C) {
    ++tot;
    if (n == 1) {
        cout << A << "->" << C << "/";
        return;
    }
    Hanoi(n - 1, A, C, B);
    cout << A << "->" << C << "/";
    Hanoi(n - 1, B, A, C);
}

int main() {
    int n;
    cin >> n;
    Hanoi(n, 'A', 'B', 'C');
    cout << '\n' << tot << '\n' << tot << '\n';
    return 0;
}

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;

const int N = 105;
int a[N][N];

int main() {
    int n, x, y, count;
    cin >> n;
    memset(a, 0, sizeof(a));
    count = a[x = 0][y = n - 1] = 1;
    while (count < n * n) {
        while (x + 1 < n && !a[x + 1][y]) a[++x][y] = ++count;
        while (y - 1 >= 0 && !a[x][y - 1]) a[x][--y] = ++count;
        while (x - 1 >= 0 && !a[x - 1][y]) a[--x][y] = ++count;
        while (y + 1 < n && !a[x][y + 1]) a[x][++y] = ++count;
    }
    for (x = 0; x < n; x++) {
        for (y = 0; y < n; y++) cout << setw(5) << a[x][y];
        cout << endl;
    }
    return 0;
}

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

string s;

int main() {
    int k; // 保证输入 0 <= k < 26
    cin >> k >> s;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        if (s[i] <= 'Z' && s[i] + k > 'Z')
            s[i] = (s[i] + k) % 'Z' + 'A' - 1;
        else if ('A' <= s[i] && s[i] <= 'Z')
            s[i] += k;
    }
    char pre;
    int st = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] < 'A' || s[i] > 'Z') {
            if (st == -1) {
                st = i;
                pre = s[i];
            } else {
                char tmp = s[i];
                s[i] = pre;
                pre = tmp;
            }
        }
    }
    if (st != -1) s[st] = pre;
    cout << s << endl;
    return 0;
}

（拓扑排序）在我们所学的课程中，部分课程之间可能存在依赖关系，如我们在学习图论知识之前，需要先学习离散数学的基础知识。一门课可能有若干先修课程。现在老师需要安排一些课程的授课计划，排课需要遵从一定的规则，即只有修习完某课程的全部先修课程后，才能修习该课程。在本例中，用1~n表示n门课程，用xy表示x是y的先修课程。输入数据保证图中没有环与重边。要求输出任意一个可行的授课顺序。图用邻接矩阵方法存储。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 105;
int a[N][N];
int in[N], s[N];
int n, m, u, v;

void Topo() {
    queue<int> q;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (①) q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        s[cnt++] = ②;
        for (int i = 1; i <= n; i++) {
            if (③) {
                ④;
                if (in[i] == 0) q.push(i);
            }
        }
    }
}

int main() {
    memset(in, 0, sizeof(in));
    memset(a, 0, sizeof(a));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        in[v]++;
        ⑤;
    }
    Topo();
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << s[i];
    }
    cout << endl;
    return 0;
}

（八皇后问题）要求用回溯法求解八皇后问题：在 $8 \times 8$ 的棋盘上放置八个皇后，确保任意两个皇后都不在同一行、同一列或同一斜线上。请输出八皇后问题的所有可行解。

#include <iostream>
#include <cmath>
using namespace std;

bool Place(int k, int i, int *x) {
    for (int j = 0; j < k; j++)
        if (x[j] == i || ①)
            return false;
    return true;
}

void NQueens(int k, int n, int *x) {
    for (int i = 0; i < n; i++)
        if (Place(k, i, x)) {
            ②;
            if (③) {
                for (int j = 0; j < n; j++) cout << x[j] << " ";
                cout << endl;
            } else {
                ④;
            }
        }
}

int main() {
    int x[8];
    for (int i = 0; i < 8; i++) x[i] = -1;
    ⑤;
    return 0;
}