当前位置: 首页 > news >正文

【蓝桥杯集训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 题目&#xff1a; 给你一个整数n 要求将1~n的所有排列情况列出 比如&#xff1a…...

Elasticsearch:构建自动补全功能 - Autocomplete

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

One UI 5.1 更新来了

之前一直在关注One UI 5.0里提到的视频通话背景功能模块&#xff0c;结果5.0版本推送的时候没有引入&#xff0c;有先行者计划博主说是5.1里肯定会有的&#xff1b;前一两天One UI 5.1更新来了&#xff0c;然而该功能还是没有引入&#xff0c;表示很遗憾&#xff1b;本次更新新…...

Python学习笔记11:文件

文件 打开文件 函数open的参数mode的最常见取值 值描述‘r’读取模式&#xff08;默认值&#xff09;‘w’写入模式‘x’独占写入模式‘a’附加模式‘b’二进制模式&#xff08;与其他模式结合使用&#xff09;‘t’文本模式&#xff08;默认值&#xff0c;与其他模式结合使…...

django-filter的使用

django-filter是一个通用的、可重用的应用程序&#xff0c;它可以减轻视图代码的编写工作量。具体来说&#xff0c;它允许用户根据模型的字段筛选查询集&#xff0c;并显示表单让他们这样做。 安装 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 七层模型 七层模型&#xff0c;亦称 OSI&#xff08;Open System Interconnection&#xff09;。OSI 七层参考模型是国际标准化组织&#xff08;ISO&#xff09;制定的一个用于计算机或通信系统间网络互联的标准体系&#xff0c;一般称为 OSI 参考模型或七层模型。OSI 七层…...

18跨越语言:不同语言间进行RPC通信

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

解压缩工具:Bandizip 中文

bandizip是一款可靠和快速的压缩软件&#xff0c;它可以解压RAR、7Z、ZIP、ISO等数十种格式&#xff0c;也可以压缩7Z、ZIP、ISO等好几种常用格式&#xff0c;在压缩文件方面毫不逊色于winrar&#xff0c;适用于多核心压缩、快速拖放、高速压缩等功能&#xff0c;采用了先进快速…...

JAVA知识点全面总结2:面向对象

二.面向对象 1.面向对象有哪些重要的关键字&#xff1f;作用是什么&#xff1f; 2.理解多态的使用&#xff1f; 3.接口与抽象类的相同点和不同点&#xff1f; 4.equals和toString的判断&#xff1f; 5.新建对象的流程是什么&#xff1f;new一个对象&#xff1f; 6.深拷贝…...

DNS作用及工作原理

文章目录1. DNS作用2 DNS 三个组成部分&#xff1a;2.1 客户端2.2Local DNS2.3 权威域 DNS 服务器3 工作过程1. DNS作用 DNS 分为 Client 和 Server&#xff0c;Client 扮演发问的角色&#xff0c;也就是问 Server 一个 Domain Name&#xff0c;而 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 开源网关再次更新啦~ 一起来看看是否有你期待的功能&#xff01; 1、协议转换功能上线 之前发布的 Apinto v0.10.0 已经支持了多协议的基本功能&#xff0c;实现多协议支持的一次验证。本次最新版本可以支持 HTTP 与 gRPC、HTTP 与 Dubbo2 之间的协议转换。…...

Android 12.0 根据app包名授予app监听系统通知权限

1.概述 在12.0的系统rom产品定制化开发中,在一些产品rom定制化开发中,系统内置的第三方app需要开启系统通知权限,然后可以在app中,监听系统所有通知,来做个通知中心的功能,所以需要授权 获取系统通知的权限,然后来顺利的监听系统通知。来做系统通知的功能 2.根据app包名…...

mysql视图和存储过程

视图视图就是将一条sql查询语句封装起来&#xff0c;之后使用sql时&#xff0c;只需要查询视图即可&#xff0c;查询视图时会将这条sql语句再次执行一遍。视图不保存数据&#xff0c;数据还是在表中。SELECT 语句所查询的表称为视图的基表&#xff0c;而查询的结果集称为虚拟表…...

uniapp 实现人脸认证

前言 对于前端来说&#xff0c;需要后端提供一个人脸识别接口&#xff0c;前端传入图片&#xff0c;接口识别并返回结果&#xff0c;如此看来&#xff0c;其实前端只需实现图片传入即可&#xff0c;但是其实不然&#xff0c;在传入图片时&#xff0c;需要进行以下几点操作&…...

自学大数据第三天~终于轮到hadoop了

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

Unity 入门精要00---Unity提供的基础变量和宏以及一些基础知识

头文件引入&#xff1a; XXPROGRAM ... #include "UnityCG.cginc"; ... ENDXX 常用的结构体&#xff08;在UnityCg.cginc文件中&#xff09;&#xff1a;在顶点着色器输入和输出时十分好用 。 关于如何使用这些结构体&#xff0c;可在Unity安装文件目录/Editor…...

Kubernetes的网络架构及其安全风险

本博客地址&#xff1a;https://security.blog.csdn.net/article/details/129137821 一、常见的Kubernetes网络架构 如图所示&#xff1a; 说明&#xff1a; 1、集群由多个节点组成。 2、每个节点上运行若干个Pod。 3、每个节点上会创建一个CNI网桥&#xff08;默认设备名称…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...