【蓝桥杯集训12】DFS(3 / 5)
目录
842. 排列数字 - DFS按位置枚举
843. n-皇后问题 - DFS按行枚举
165. 小猫爬山 - DFS枚举小猫
1209. 带分数 - DFS
3502. 不同路径数 -
842. 排列数字 - DFS按位置枚举
活动 - AcWing
题目:
给你一个整数n
要求将1~n的所有排列情况列出
比如:n=3
则123 132 213 231……
思路:
dfs从0位置开始枚举 层层深入 每枚举完一种情况就回溯
/**道阻且长,行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N=100010;static int[] st=new int[N];static int[] path=new int[N];static int n;static void dfs(int u) //枚举每一个位置{if(u==n) //位置从0 1 2……开始 如果u==n说明位置已经填满 需要输出{for(int i=0;i<n;i++) wt.print(path[i]+" ");wt.println();}for(int i=1;i<=n;i++)if(st[i]==0){path[u]=i;st[i]=1;dfs(u+1);st[i]=0; //还原现场}}public static void main(String[] args) throws IOException{n=rd.nextInt();dfs(0);wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}
843. n-皇后问题 - DFS按行枚举
活动 - AcWing
题目:
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上
现在给定整数 n,请你输出所有的满足条件的棋子摆法
思路:
这题思路和排列的dfs思路如出一辙
从第0行开始按行枚举,这样保证每一行只有一个棋子
- 在某行情况下枚举每一列,如果该列、主对角线、副对角线上均没有棋子
- 则把棋子放在该位置,递归这种情况下 下一行的棋子摆放位置
- 当枚举行数==n时,因为是从第0行开始枚举,说明一个棋盘的棋子已经摆好
- 则输出这种情况,然后回溯还原现场,继续输出下一种情况
- 不断回溯递归,直到输出所有情况
对于主对角线和副对角线的标记
我们可以通过dg[x+y] udg[y-x+n]映射得到
/**道阻且长,行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N=20;static int[] col=new int[N],dg=new int[N],udg=new int[N];static char[][] g=new char[N][N];static int n;static void dfs(int u) //枚举每一个位置{if(u==n) //从0 1 2……行开始枚举 如果u==n说明棋盘已经摆满 需要输出{for(int i=0;i<n;i++){for(int j=0;j<n;j++)wt.print(g[i][j]);wt.println();}wt.println();return;}for(int i=0;i<n;i++)if(col[i]==0&&dg[i+u]==0&&udg[i-u+n]==0){g[u][i]='Q';col[i]=dg[i+u]=udg[i-u+n]=1;dfs(u+1);col[i]=dg[i+u]=udg[i-u+n]=0;g[u][i]='.';}}public static void main(String[] args) throws IOException{n=rd.nextInt();for(int i=0;i<n;i++)for(int j=0;j<n;j++) g[i][j]='.';dfs(0);wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}
165. 小猫爬山 - DFS枚举小猫
活动 - AcWing
题目:
一共n只小猫,每只小猫重wi
一辆缆车最大承重为m
问最少雇多少辆车能把所有猫都装上?
思路:
总思路就是枚举所有情况的车数,取最小值
从第0只小猫开始枚举,dfs(小猫数,当前车数)
每次塞猫分两种情况:
- 在已开好的车内,如果塞的下,塞进去,并递归这种情况下其他情况
- 开好的所有车都装不下,则开新车,车数+1,并递归这种情况下的其他情况
因为要枚举所有情况,所以每次递归完后,回溯时要还原现场
当所有小猫枚举完后,更新最小的车数
优化点1:想要车越少,则先让重的猫上车,这样不会遇到塞不下多开新车,能优化搜索速度
优化点2:如果搜索到的答案 ≥ 目前的res 则不用继续搜索,因为再搜索也不是最优解
/**道阻且长,行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N=20;static int[] a=new int[N],car=new int[N];static int n,w;static int res=N;public static void dfs(int cat,int bus){if(bus>=res) return;if(cat==n){res=Math.min(res,bus);return;}for(int i=0;i<bus;i++) //如果当前车可以塞的下if(car[i]+a[cat]<=w){car[i]+=a[cat];dfs(cat+1,bus);car[i]-=a[cat];}//如果所有开好的车都塞不下 则开新车car[bus]=a[cat];dfs(cat+1,bus+1);car[bus]=0;}public static void main(String[] args) throws IOException{n=rd.nextInt();w=rd.nextInt();for(int i=0;i<n;i++) a[i]=rd.nextInt();Arrays.sort(a,0,n);for(int i=0,j=n-1;i<j;i++,j--){int t=a[i];a[i]=a[j];a[j]=t;}dfs(0,0); //dfs(小猫数,车数) 小猫和车都从0开始枚举wt.print(res);wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}
1209. 带分数 - DFS
活动 - AcWing
题目:
思路:
3502. 不同路径数 -
3502. 不同路径数 - AcWing题库
题目:
思路:
相关文章:

【蓝桥杯集训12】DFS(3 / 5)
目录 842. 排列数字 - DFS按位置枚举 843. n-皇后问题 - DFS按行枚举 165. 小猫爬山 - DFS枚举小猫 1209. 带分数 - DFS 3502. 不同路径数 - 842. 排列数字 - DFS按位置枚举 活动 - AcWing 题目: 给你一个整数n 要求将1~n的所有排列情况列出 比如:…...

Elasticsearch:构建自动补全功能 - Autocomplete
什么是自动补全(autocomplete)功能呢?我们举一个很常见的例子。 每当你去谷歌并开始打字时,就会出现一个下拉列表,其中列出了建议。 这些建议与查询相关并帮助用户完成查询。 Autocomplete 正如维基百科所说的…...

One UI 5.1 更新来了
之前一直在关注One UI 5.0里提到的视频通话背景功能模块,结果5.0版本推送的时候没有引入,有先行者计划博主说是5.1里肯定会有的;前一两天One UI 5.1更新来了,然而该功能还是没有引入,表示很遗憾;本次更新新…...
Python学习笔记11:文件
文件 打开文件 函数open的参数mode的最常见取值 值描述‘r’读取模式(默认值)‘w’写入模式‘x’独占写入模式‘a’附加模式‘b’二进制模式(与其他模式结合使用)‘t’文本模式(默认值,与其他模式结合使…...
django-filter的使用
django-filter是一个通用的、可重用的应用程序,它可以减轻视图代码的编写工作量。具体来说,它允许用户根据模型的字段筛选查询集,并显示表单让他们这样做。 安装 pip install django-filter快速开始 在settings.py中添加如下配置: INSTAL…...

时序预测 | MATLAB实现IWOA-BiLSTM和BiLSTM时间序列预测(改进的鲸鱼算法优化双向长短期记忆神经网络)
时序预测 | MATLAB实现IWOA-BiLSTM和BiLSTM时间序列预测(改进的鲸鱼算法优化双向长短期记忆神经网络) 目录时序预测 | MATLAB实现IWOA-BiLSTM和BiLSTM时间序列预测(改进的鲸鱼算法优化双向长短期记忆神经网络)预测效果基本介绍程序设计参考资料预测效果 基本介绍 MATLAB实现IWO…...

【C++】string的成员函数、成员常量和非成员函数
目录 string 1. string的成员函数 1.1 构造、析构和赋值运算符重载 1.1.1 构造函数 1.1.2 析构函数 1.1.3 赋值运算符重载 1.2 迭代器 1.3 容量 1.4 元素访问 1.4.1 遍历方法 1.5 修改器 1.6 字符串操作 2. string的成员常量 3. string的非成员函数 string 以下…...

网络互连模型:OSI 七层模型
OSI 七层模型 七层模型,亦称 OSI(Open System Interconnection)。OSI 七层参考模型是国际标准化组织(ISO)制定的一个用于计算机或通信系统间网络互联的标准体系,一般称为 OSI 参考模型或七层模型。OSI 七层…...

18跨越语言:不同语言间进行RPC通信
在最开始介绍gRPC时我们讲到,gRPC具有灵活的兼容性,可以支持很多种编程语言,下面我们就使用在后端领域最常用的两种编程语言Go和Java,来体验一下gRPC在不同语言的项目间是如何进行通信的。 逻辑架构 由上图我们可以看出,Go语言设计gRPC的服务端,Java语言设计gRPC的客户端…...

解压缩工具:Bandizip 中文
bandizip是一款可靠和快速的压缩软件,它可以解压RAR、7Z、ZIP、ISO等数十种格式,也可以压缩7Z、ZIP、ISO等好几种常用格式,在压缩文件方面毫不逊色于winrar,适用于多核心压缩、快速拖放、高速压缩等功能,采用了先进快速…...
JAVA知识点全面总结2:面向对象
二.面向对象 1.面向对象有哪些重要的关键字?作用是什么? 2.理解多态的使用? 3.接口与抽象类的相同点和不同点? 4.equals和toString的判断? 5.新建对象的流程是什么?new一个对象? 6.深拷贝…...

DNS作用及工作原理
文章目录1. DNS作用2 DNS 三个组成部分:2.1 客户端2.2Local DNS2.3 权威域 DNS 服务器3 工作过程1. DNS作用 DNS 分为 Client 和 Server,Client 扮演发问的角色,也就是问 Server 一个 Domain Name,而 Server 必须要回答此 Domain…...
Android 9.0 wifi的随机mac地址修改为固定不变
1.前言 在9.0的系统rom产品定制化开发中,在系统默认的wifi的mac地址是会在联网前后会变化,因为默认是随机显示mac地址,所以会在连上wifi后mac地址会变动但是如果根据mac地址来升级 会引起一系列问题,为了避免这些问题 所以就要求固定mac地址,这就需要看wifi模块怎么改变ma…...

Apinto 网关 V0.11.1 版本发布,多协议互转,新增编码转换器,接入 Prometheus
Eolink 旗下 Apinto 开源网关再次更新啦~ 一起来看看是否有你期待的功能! 1、协议转换功能上线 之前发布的 Apinto v0.10.0 已经支持了多协议的基本功能,实现多协议支持的一次验证。本次最新版本可以支持 HTTP 与 gRPC、HTTP 与 Dubbo2 之间的协议转换。…...
Android 12.0 根据app包名授予app监听系统通知权限
1.概述 在12.0的系统rom产品定制化开发中,在一些产品rom定制化开发中,系统内置的第三方app需要开启系统通知权限,然后可以在app中,监听系统所有通知,来做个通知中心的功能,所以需要授权 获取系统通知的权限,然后来顺利的监听系统通知。来做系统通知的功能 2.根据app包名…...

mysql视图和存储过程
视图视图就是将一条sql查询语句封装起来,之后使用sql时,只需要查询视图即可,查询视图时会将这条sql语句再次执行一遍。视图不保存数据,数据还是在表中。SELECT 语句所查询的表称为视图的基表,而查询的结果集称为虚拟表…...
uniapp 实现人脸认证
前言 对于前端来说,需要后端提供一个人脸识别接口,前端传入图片,接口识别并返回结果,如此看来,其实前端只需实现图片传入即可,但是其实不然,在传入图片时,需要进行以下几点操作&…...

自学大数据第三天~终于轮到hadoop了
前面那几天是在找大数据的门,其实也是在搞一些linux的基本命令,现在终于轮到hadoop了 Hadoop hadoop的安装方式 单机模式: 就如字面意思,在一台机器上运行,存储是采用本地文件系统,没有采用分布式文件系统~就如我们一开始入门的时候都是从本地开始的; 伪分布式模式 存储采用…...

Unity 入门精要00---Unity提供的基础变量和宏以及一些基础知识
头文件引入: XXPROGRAM ... #include "UnityCG.cginc"; ... ENDXX 常用的结构体(在UnityCg.cginc文件中):在顶点着色器输入和输出时十分好用 。 关于如何使用这些结构体,可在Unity安装文件目录/Editor…...

Kubernetes的网络架构及其安全风险
本博客地址:https://security.blog.csdn.net/article/details/129137821 一、常见的Kubernetes网络架构 如图所示: 说明: 1、集群由多个节点组成。 2、每个节点上运行若干个Pod。 3、每个节点上会创建一个CNI网桥(默认设备名称…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...