🎆音乐分享（点击链接可以听哦）
目录
⭐什么是dfs
就是深度优先遍历，顾名思义，就是沿着一条路一直走到头，然后再回头
具体方法请看下面的题目
🚥🚥🚥🚥🚥🚥
排列型枚举（全排列）
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
从一条路遍历到头后，然后再回溯
#include<iostream>
using namespace std;
const int N=100100;
int a[N],b[N];
int n,m;
void dfs(int x)
{
if(x==m+1)
{
for(int i=1;i<=m;i++)
{
printf("%d ",a[i]);
}
return;
}
for(int i=1;i<=m;i++)
{
if(b[i]==0)
{
a[x]=i;//这里是x
b[i]=1;
dfs(x+1);
b[i]=0;
}
}
return;
}
int main()
{
cin>>m;
dfs(1);
}
🚕🚕🚕🚕🚕🚕
排列型枚举（全排列变形）
1537. 递归实现排列类型枚举 II – AcWing题库
给定一个长度为 n 的可包含重复数字的序列，请你求出其所有不重复的全排列。
输入格式
第一行包含整数 n。
第二行包含 n个整数。
输出格式
输出所有的不同排列，每种排列占一行。
在确定每种排列的输出顺序时，第一个数较小的先输出，第一个数相同时，第二个数较小的先输出，以此类推
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
int a[N], nums[N];
bool st[N];
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i ++ ) cout << nums[i] << ' ';
cout << endl;
return;
}
for (int i = 0; i < n; i ++ )
if (!st[i])
{
nums[u] = a[i];
st[i] = true;
dfs(u + 1);
st[i] = false; //还原现场
while (i + 1 < n && a[i + 1] == a[i]) i ++ ; //跳过重复的
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n); //排序后重复的数字就会排在一起，便于去重
dfs(0);
return 0;
}🚕🚕🚕🚕🚕🚕
组合型枚举
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面
（例如
1 3 5 7排在1 3 6 8前面）。
#include <iostream>
using namespace std;
int n,m;
const int N=100010;
int a[N],b[N];
void dfs(int x, int start)
{
if(x+n-start < m)
return;
if(x == m+1)
{
for(int i = 1; i <= m; i++)
printf("%d ", a[i]);
puts("");
return;
}
for(int i = start; i <= n; i++)// i从start开始 i<= n
{
if(b[i]==0)
{
a[x]=i;//是x
b[i]=1;
dfs(x+1, i+1);
b[i]=0;
}
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
dfs(1, 1);
return 0;
}
🚕🚕🚕🚕🚕🚕
指数型枚举
92. 递归实现指数型枚举 – AcWing题库
题目描述
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。输入格式
输入一个整数n。输出格式
每行输出一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
#include <iostream>
using namespace std;
typedef long long ll;
int n;
int a[20];
bool vis[20];
// 一共tar个坑，当前枚举到第pos个坑
void dfs(int pos, int tar) {
if (pos == tar + 1) {
for (int i = 1; i <= tar; i ++ ) cout << a[i] << " ";
cout << endl;
return ;
}
// 选数填坑
for (int i = 1; i <= n; i ++) {
if (!vis[i]) {
vis[i] = true; a[pos] = i;
dfs (pos + 1, tar);
vis[i] = false;
}
}
}
int main() {
cout << endl; // 不取
cin >> n;
for (int i = 1; i <= n; i ++ )//主要是这一步，控制了每次取的数字个数不同
dfs(1, i);
return 0;
}
🚕🚕🚕🚕🚕🚕
dfs的应用
给定两个整数 n,x。
你可以对 x 进行任意次以下操作：
- 选择 x 的一位数字 y，将 x 替换为 x*y。
请你计算通过使用上述操作，将 x变为一个 n 位数字（不含前导 0），所需要的最少操作次数。
例如，当 n=3,x=2时，对 2 进行如下 4 次操作，即可使其变为 3 位数字：
- 将 2 替换为 2×2=4。
- 将 4 替换为 4×4=16。
- 将 16 替换为 16×6=96。
- 将 96 替换为 96×9=864。
输入格式
共一行，包含两个整数 n,x。
输出格式
一个整数，表示将 x 变为一个 n 位数字，所需要的最少操作次数。
如果无解，则输出
-1。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1000;
int n;
int ans = INF;
void dfs(LL x, int d)
{
bool st[10] = {0};
int cnt = 0;
for (LL y = x; y; y /= 10)
{
cnt ++ ;
st[y % 10] = true;//把不同位数分开
}
if (d + n - cnt >= ans) return;//如果当前位数+结果要求的位数-当前的位数>=结果，不成立，结束运行
if (cnt == n)
{
ans = d;
return;
}
for (int i = 9; i >= 2; i -- )
if (st[i])//如果存在这个位数
dfs(x * i, d + 1);
}
int main()
{
LL x;
cin >> n >> x;
dfs(x, 0);
if (ans == INF) ans = -1;
cout << ans << endl;
return 0;
}🚕🚕🚕🚕🚕🚕
Code over!
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/131359.html
