CSP-S 提高级 · CSP 2025 提高级第一轮 第 16 题

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

#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;
}

判断题

16. (1 分) 当输入的 $n=3$ 的时候，程序输出的答案为 3。 17. 在 dfs 函数运行过程中，$k$ 的取值会满足 $1 \leq k \leq n+1$。 18. 删除第 19 行的 flag[i]=false;，对答案不会产生影响。

选择题

19. 当输入的 $n=4$ 的时候，程序输出的答案为（ ）。

• A. $11$
• B. $12$
• C. $24$
• D. $9$

20. 如果因为某些问题，导致程序运行第 25 行的 dfs 函数之前，数组 p 的初值并不全为 0，则对程序的影响是（ ）。

• A. 输出的答案比原答案要小
• B. 无法确定输出的答案
• C

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是 DFS 回溯枚举排列，但加了一条‘禁止后一个数比前一个大 1'的限制。拿到题先想：n=3 时暴力列一下所有排列，划掉含'1,2'或'2,3'的，数剩下的个数；再想代码里哪几行在干这事，特别是 flag 的标记与恢复、p 数组的访问时机。

最容易把‘禁止连续递增对’理解成‘禁止相邻数字’或‘禁止递增’，导致把合法排列误删。其次是忽略回溯中 flag[i]=false 的作用，以为删了它只是少算几个，其实会导致整棵搜索树状态污染，合法解全漏。还有人在判断 p 数组初值影响时，只盯着 k=1 的情况，忘了 k>1 时 p[k-1] 早已在上一层被赋值，初值根本用不上。

考察知识点

算法 — DFS / 回溯法 / 排列生成

概念定义

• DFS（深度优先搜索）：用递归一层层往下钻，把能走的路都走到头。
• 回溯法：走到死胡同或发现当前分支不合法时，撤销刚才的选择（把标记去掉），再试别的路。

逐步推导

核心逻辑

代码在枚举 1~n 的所有排列，但多了一个判断：if (k > 1 && i == p[k - 1] + 1) continue; 意思是：当前要填的位置 k，如果选的数字 i 恰好等于上一个位置 k-1 的数字加 1，就跳过。也就是说，排列里不能出现形如 (x, x+1) 的相邻对。