Day10-C4 回溯专项（GESP高等级风格）

独立训练选择、递归、撤销、排列数量与剪枝。程序统计1到n的全排列数量。

#include <iostream>
#include <vector>
using namespace std;
int n,cnt=0; vector<int> used;
void search(int step){
    if(step==n){++cnt;return;}
    for(int x=1;x<=n;++x){
        if(used[x]) continue;
        used[x]=1;
        search(step+1);
        used[x]=0;
    }
}
int main(){cin>>n;used.assign(n+1,0);search(0);cout<<cnt;}

第 1 题

回溯的典型结构是（ ）。

{{ select(1) }}

• 预处理、区间做差
• 统计入度、删边
• 入队、出队、最短路
• 选择、递归、撤销

第 2 题

used[x] 表示（ ）。

{{ select(2) }}

• x的最短距离
• x的入度
• x的前缀和
• 数字x是否已在当前方案中使用

第 3 题

递归返回后执行 used[x]=0 的目的是（ ）。

{{ select(3) }}

• 恢复状态供其他分支使用
• 删除输入
• 结束程序
• 增加答案

第 4 题

step==n 表示（ ）。

{{ select(4) }}

• 已经完成一个长度为n的排列
• 前缀和完成
• 队列为空
• 图中存在环

第 5 题

输入 3，程序输出（ ）。

{{ select(5) }}

• 8
• 6
• 9
• 3

第 6 题

若删除 if(used[x]) continue，程序将统计（ ）。

{{ select(6) }}

• 拓扑序
• 无向图连通分量
• 允许重复选择的长度n序列
• 区间和

第 7 题

不考虑常数，程序枚举规模约为（ ）。

{{ select(7) }}

• $O(n)$
• $O(\log n)$
• $O(n!)$
• $O(1)$

第 8 题

在不能再得到合法答案时提前返回，称为（ ）。

{{ select(8) }}

• 建表
• 剪枝
• 域名解析
• 链接