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

题目

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

假如删去第 14 行的 if(flag[i]) continue;，输入 3，得到的输出答案是（ ）。

选项

• A. $27$
• B. $3$
• C. $16$
• D. $12$

答案

C

题解

选 C，输出为 \(16\)。

删去 if(flag[i]) continue; 后，数字可以重复使用，所以程序枚举的是长度为 3、每个位置都取 \(1,2,3\) 的序列，共有 \[ 3^3=27 \] 种。

但下面的判断仍然保留： ``cpp if (k > 1 && i == p[k - 1] + 1) continue; ` 它表示：后一个数不能恰好比前一个数大 1。因此，相邻的 12 和 23` 都不允许出现。

从 27 种中扣除不合法的序列：

• 前两位是 12 或 23：第三位任取，共 \(2\times3=6\) 种。
• 后两位是 12 或 23：第一位任取，共 \(3\times2=6\) 种。
• 123 同时属于上述两类，被减了两次，需要加回来一次。

所以最终答案为 \[ \boxed{27-6-6+1=16}. \]