DFS全排列问题整理
2025-03-26 18:46:33
发布于：上海
3阅读
0回复
0点赞
食用说明一号:只是一个整理,主播本人可能理解并不透彻,只是为了捋一下思路做得这篇笔记...
食用说明二号:对于看过DFS笔记全整理那篇的同学,可以直接跳过抽奖们,去看后面一些没有提到过的题目哦!
(适合有DFS基础的同学,可以一起讨论哦,如果觉得有问题也可以直接提出,主播一定会更改哒!)
正文开始:
1.抽奖2:额...很熟悉的题目了,在笔记那篇就已经反复鞭尸了:
是可以重复的
直接存储,输出
重点代码:
if(x==n+1){
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
a[x]=i;
dfs(x+1);
}
这里有同学会有疑问:为什么是
if(x==n+1)
而不是
if(x==n)
(呵呵,祖传的问题)
因为主播这里是从
dfs(1)
开始的.本来就是从1开始.
那么,为了能让这个递归能运行n次,判断里肯定要填n+1啦
2.抽将3:
记录编号无放回 ---> 加入vis数组去标记曾经抽到过的球.
重点代码:
if(x==n+1){
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(!b[i]){
b[i]=1;
a[x]=i;
dfs(x+1);
b[i]=0;
}
}
3.抽将4:
相比抽将2多施加了2个条件:一个是抽m个球,一个是和为h
第二个很好解决.
抽m个球也不难:只要把判断
if(x==n+1)
改成
if(x==m+1)
就可以了(这个if就是为了判断它有没有抽足够次数的奖,只要把里面的n改成m就可以让它只抽m次了)
核心代码:
if(x==m+1){
int sum=0;
for(int i=1;i<=m;i++){
sum+=a[i];
}
if(sum==p)answer++;
return;
}
for(int i=1;i<=n;i++){
a[x]=i;
dfs(x+1);
}
*本来还有一个抽奖5,这里不说了,换汤不换药,又想写的同学可以自己去做一做哦
这里空空如也
有帮助，赞一个