深度优先搜索题目合集

embedded/2024/11/26 0:32:16/

 本片为洛谷题目

 纯手打,请您放心食用!

目录

U121029 全排列(可重复)

题目描述

输入格式

输出格式

输入输出样例

题解

P1157 组合的输出

题目描述

输入格式

输出格式

输入输出样例

题解

P2404 自然数的拆分问题

题目描述

输入格式

输出格式

输入输出样例

说明/提示


U121029 全排列(可重复)

题目描述

输入n,从1~n的数可重复的排列:(n<9) 例如:n=3

1 1 1

1 1 2

1 1 3

1 2 1

1 2 2

1 2 3

1 3 1

……

3 3 3

输入格式

输入n

输出格式

输出所有排列。

输入输出样例

输入 #1

3

输出 #1

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2 
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

题解

#include<bits/stdc++.h>
using namespace std;
int n,a[11];
void bfs(int g){if(g>n){for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;return;	}for(int i=1;i<=n;i++){a[g]=i;bfs(g+1);}
}
int main(){cin>>n;bfs(1);return 0;
}

P1157 组合的输出

题目描述

排列与组合是常用的数学方法,其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r≤n),我们可以简单地将 n 个元素理解为自然数 1,2,…,n,从中任取 r 个数。

现要求你输出所有组合。

例如 n=5,r=3,所有组合为:

123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。

输入格式

一行两个自然数 n,r(1<n<21,0≤r≤n)。

输出格式

所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占三个字符的位置,所有的组合也按字典顺序。

注意哦!输出时,每个数字需要 3 个场宽。以 C++ 为例,你可以使用下列代码:

cout << setw(3) << x;

输出占 33 个场宽的数 x。注意你需要头文件 iomanip

输入输出样例

输入 #1

5 3 

输出 #1

  1  2  31  2  41  2  51  3  41  3  51  4  52  3  42  3  52  4  53  4  5

题解

#include<bits/stdc++.h>
using namespace std;
int n,r,a[21];
void bfs(int g){if(g>r){for(int i=1;i<=r;i++)cout<<setw(3)<<a[i];cout<<endl;return;	}for(int i=a[g-1]+1;i<=n;i++){a[g]=i;bfs(g+1);}
}
int main(){cin>>n>>r;bfs(1);return 0;
}

P2404 自然数的拆分问题

题目描述

任何一个大于 11 的自然数 n,总可以拆分成若干个小于 n 的自然数之和。现在给你一个自然数 n,要求你求出 n 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列,其中字典序小的序列需要优先输出。

输入格式

输入:待拆分的自然数 n。

输出格式

输出:若干数的加法式子。

输入输出样例

输入 #1

7

输出 #1

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

说明/提示

数据保证,2≤n≤8

题解

#include<bits/stdc++.h>
using namespace std;
int n,a[11]={1},sum=0;
void bfs(int g,int sum){if(sum==n&&g>2){for(int i=1;i<=g-2;i++)cout<<a[i]<<"+";cout<<a[g-1]<<endl;return;}for(int i=a[g-1];i<=n-sum;i++){a[g]=i;sum+=i;bfs(g+1,sum);sum-=i;}
}
int main(){cin>>n;bfs(1,0);return 0;
}

P1706 全排列问题

题目描述

按照字典序输出自然数 11 到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由 1∼n 组成的所有不重复的数字序列,每行一个序列。

每个数字保留 55 个场宽。

输入输出样例

输入 #1

3

输出 #1

    1    2    31    3    22    1    32    3    13    1    23    2    1

说明/提示

1≤n≤9。

题解

#include<bits/stdc++.h>
using namespace std;
int n,a[11];
bool f[11];
void bfs(int g){if(g>n){for(int i=1;i<=n;i++)cout<<setw(5)<<a[i];cout<<endl;return;}for(int i=1;i<=n;i++){if(f[i]==false){f[i]=true;a[g]=i;bfs(g+1);f[i]=false;}}
}
int main(){cin>>n;bfs(1);return 0;
}

P1657 选书

题目描述

学校放寒假时,信息学奥赛辅导老师有 1,2,3,⋯,x 本书,要分给参加培训的 x 个人,每人只能选一本书,但是每人有两本喜欢的书。

老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本,希望设计一个程序帮助老师求出所有可能的分配方案,使每个学生都满意。

输入格式

第 11 行一个数 x。

第 22 行至第 1+x 行,每行两个数,表示 ai​ 喜欢的书的序号。

输出格式

只有一个数,总方案数 total。

输入输出样例

输入 #1

5
1 3
4 5
2 5
1 4
3 5

输出 #1

2

说明/提示

数据范围及约定

对于全部数据,1≤x≤20。

update 2022/03/07update 2022/03/07,阮行止

本题原始数据中,最后一个数据点的 x 为 0,期望输出为 0。考虑到这个数据不合理,予以删去。现在提交这个题目不会遇到 x=0 的数据点。

题解

#include<bits/stdc++.h>
using namespace std;
int n,a[21],b[21],sum=0;
bool f[21];
void bfs(int g){if(g>n){sum++;return;}if(f[a[g]]==false){f[a[g]]=true;bfs(g+1);f[a[g]]=false;}if(f[b[g]]==false){f[b[g]]=true;bfs(g+1);f[b[g]]=false;}
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i]>>b[i];bfs(1);cout<<sum;return 0;
}

P1036 [NOIP2002 普及组] 选数

题目描述

已知 n 个整数 x1​,x2​,⋯,xn​,以及 11 个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,44 个整数分别为 3,7,12,193,7,12,19 时,可得全部的组合与它们的和为:

3+7+12=223+7+12=22

3+7+19=293+7+19=29

7+12+19=387+12+19=38

3+12+19=343+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:3+7+19=293+7+19=29。

输入格式

第一行两个空格隔开的整数 n,k(1≤n≤20,k<n)。

第二行 n 个整数,分别为 x1​,x2​,⋯,xn​(1≤xi​≤5×10^6)。

输出格式

输出一个整数,表示种类数。

输入输出样例

输入 #1

4 3
3 7 12 19

输出 #1

1

说明/提示

【题目来源】

NOIP 2002 普及组第二题

题解

#include<bits/stdc++.h>
using namespace std;
int n,r,a[21],b[21],c[21],ans=0;
bool func(int n){if(n<=1)return false;for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;return true;
}
void bfs(int g){if(g>r){int temp=0;for(int i=1;i<=r;i++)temp+=c[i];ans+=func(temp);return;	}for(int i=b[g-1]+1;i<=n;i++){b[g]=i;c[g]=a[i];bfs(g+1);c[g]=0;}
}
int main(){cin>>n>>r;for(int i=1;i<=n;i++)cin>>a[i];bfs(1);cout<<ans;return 0;
}


http://www.ppmy.cn/embedded/140513.html

相关文章

鸿蒙NEXT开发-Navigation组件导航

注意&#xff1a;博主有个鸿蒙专栏&#xff0c;里面从上到下有关于鸿蒙next的教学文档&#xff0c;大家感兴趣可以学习下 如果大家觉得博主文章写的好的话&#xff0c;可以点下关注&#xff0c;博主会一直更新鸿蒙next相关知识 专栏地址: https://blog.csdn.net/qq_56760790/…

Spark SQL操作

Spark SQL操作 文章目录 Spark SQL操作一、DataFrame的创建与保存1.前提操作2.数据准备3.创建4.保存DataFrame 二、DataFrame的操作1.printSchema2.show3.select4.filter5.groupBy(filed)6.sort(field) 三、临时表操作1.创建临时表2.通过临时表及SQL语句进行查询 四、从RDD转换…

Python 使用 OpenCV 将 MP4 转换为 GIF图

以下是使用 Python 和 OpenCV 将 MP4 转换为 GIF 的示例代码&#xff1a; python import cv2 import imageiodef mp4_to_gif(mp4_path, gif_path, fps10, start_timeNone, end_timeNone):"""将MP4视频转换为GIF动图。:param mp4_path: 输入MP4视频的路径。:pa…

疑难Tips:NextCloud域名访问登录时卡住,显示违反内容安全策略

[ 知识是人生的灯塔,只有不断学习,才能照亮前行的道路 ] 1使用域名访问Nextcloud用户登录时卡住,显示违反内容安全策略 我使用官方Docker镜像来部署NextCloud 28.0.5,并通过Openresty反向代理Nextcloud,但是在安装后无法稳定工作,每次登录后,页面会卡死在登录界面,无法…

设计模式-创建型-抽象工厂模式

1.概念 工厂方法模式只能生产一个产品系列&#xff0c;抽象工厂可以生产多个产品系列 2.作用 多个具体产品组成一个产品族&#xff08;产品系列&#xff09;&#xff0c;一个具体工厂负责生产一个产品族 3.应用场景 系统所需产品间由依赖关系&#xff0c;可以划分为同一产…

Java教程:SE进阶【十万字详解】(下)

✨博客主页&#xff1a; https://blog.csdn.net/m0_63815035?typeblog &#x1f497;《博客内容》&#xff1a;.NET、Java.测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 &#x1f4e2;博客专栏&#xff1a; https://blog.csdn.net/m0_63815035/cat…

Linux——1_系统的延迟任务及定时任务

系统的延迟任务及定时任务 在系统中我们的维护工作大多数时在服务器行对闲置时进行 我们需要用延迟任务来解决自动进行的一次性的维护 延迟任务时一次性的&#xff0c;不会重复执行 当延迟任务产生输出后&#xff0c;这些输出会以邮件的形式发送给延迟任务发起者 在RHEL9中…

CSV文件数据导入hive

一、加载CSV文件数据到hive表步骤&#xff1a; 1、Hive上建表&#xff0c;通常会指定字段分隔符为逗号&#xff08;row format delimited fields terminated by ‘,’ &#xff09; 2、导入CSV文件 二、实操 以csv 文件中出现字段中含有逗号的场景为例&#xff1a;{“2020”…