深度优先搜索题目合集

news/2024/11/26 3:25:53/

 本片为洛谷题目

 纯手打,请您放心食用!

目录

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/news/1549973.html

相关文章

设计模式之 桥接模式

桥接模式&#xff08;Bridge Pattern&#xff09;是一种结构型设计模式&#xff0c;其核心思想是将抽象部分和实现部分分离&#xff0c;使它们可以独立地变化。通过桥接模式&#xff0c;抽象部分和实现部分可以独立扩展&#xff0c;从而避免了继承层次过深和高耦合的问题。 桥…

#渗透测试#SRC漏洞挖掘#网络运维# 黑客脚本编写终章之重定向与脚本调用

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…

【贪心算法】贪心算法四

贪心算法四 1.最长回文串2.增减字符串匹配3.分发饼干4.最优除法 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 1.最长回文串 题目链接&…

Flutter将应用打包发布到App Store

使用Flutter将应用打包发布到App Store的详细步骤及流程图&#xff1a; 流程图 #mermaid-svg-X09iOP2FtRxwKsWw {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-X09iOP2FtRxwKsWw .error-icon{fill:#552222;}#mermai…

IDEA+Docker一键部署项目SpringBoot项目

文章目录 1. 部署项目的传统方式2. 前置工作3. SSH配置4. 连接Docker守护进程5. 创建简单的SpringBoot应用程序6. 编写Dockerfile文件7. 配置远程部署7.1 创建配置7.2 绑定端口7.3 添加执行前要运行的任务 8. 部署项目9. 开放防火墙的 11020 端口10. 访问项目11. 可能遇到的问题…

C语言练习.if.else语句.strstr

今天在做题之前&#xff0c;先介绍一下&#xff0c;新学到的库函数strstr 想要使用它&#xff0c;要先给它一个头文件<string.h> char *strstr(const char*str1,const char*str2); 首先&#xff1a;1.strstr的返回值是char&#xff0c;字符类型的。 2.两个实参&#xff…

2025-2026财年美国CISA国际战略规划(下)

文章目录 前言四、加强综合网络防御&#xff08;一&#xff09;与合作伙伴共同实施网络防御&#xff0c;降低集体风险推动措施有效性衡量 &#xff08;二&#xff09;大规模推动标准和安全&#xff0c;以提高网络安全推动措施有效性衡量 &#xff08;三&#xff09;提高主要合作…

k8s1.30.0高可用集群部署

负载均衡 nginx负载均衡 两台nginx负载均衡 vim /etc/nginx/nginx.conf stream {upstream kube-apiserver {server 192.168.0.11:6443 max_fails3 fail_timeout30s;#server 192.168.0.12:6443 max_fails3 fail_timeout30s;#server 192.168.0.13:6443 max_fails3…