CSP-S 2025 第一轮 第16题：程序阅读第 1 题 · 第 1 小题

题目

#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k - 1] + 1) continue;
        p[k] = i;
        flag[i] = true;
        dfs(k + 1);
        flag[i] = false;
    }
    return;
}
int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

(1 分) 当输入的 $n=3$ 的时候，程序输出的答案为 3。

选项

• T. 正确
• F. 错误

答案

T

题解

选 T．正确。

dfs 枚举 1～n 的所有排列，其中：

• flag[i] 保证每个数只使用一次。
• i == p[k - 1] + 1 时跳过，表示后一个数不能恰好比前一个数大 1。
• 每找到一个完整的合法排列，ans 就加 1。

当 n = 3 时：

合法排列共 3 个，所以输出 3。注意，3→2 这样的递减相邻是允许的。