【回溯专题part1】【蓝桥杯备考训练】:n-皇后问题、木棒、飞机降落【已更新完成】

目录

1、n-皇后问题(回溯模板)

2、木棒(《算法竞赛进阶指南》、UVA307)

3、飞机降落(第十四届蓝桥杯省赛C++ B组)


1、n-皇后问题(回溯模板)

n皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

1_597ec77c49-8-queens.png

现在给定整数 n,请你输出所有的满足条件的棋子摆法。

输入格式

共一行,包含整数 n。

输出格式

每个解决方案占 n 行,每行输出一个长度为 n的字符串,用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例:
4
输出样例:
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..
思路:

经典的模板,这里的u代表行、col数组用来枚举标记列、dg用来枚举标记对角线、undg用来标记反对角线

代码:
#include<bits/stdc++.h>using namespace std;int n;const int N=10;char g[N][N];bool col[N],dg[N],undg[N];void dfs(int u)
{if(u==n)//找到一种方案 {for(int i=0;i<n;i++)puts(g[i]);puts("");return ;}for(int i=0;i<n;i++)//枚举列 {if(!col[i]&&!dg[u+i]&&!undg[u-i+n]){g[u][i]='Q';col[i]=dg[u+i]=undg[u-i+n]=true;dfs(u+1);col[i]=dg[u+i]=undg[u-i+n]=false;g[u][i]='.';}}
}
int main()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]='.';dfs(0);return 0;	
} 

2、木棒(《算法竞赛进阶指南》、UVA307)

乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 50 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序,帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据,每组数据包括两行。

第一行是一个不超过 64 的整数,表示砍断之后共有多少节木棍。

第二行是截断以后,所得到的各节木棍的长度。

在最后一组数据之后,是一个零。

输出格式

为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 50。

输入样例:
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例:
6
5
思路:
关键剪枝条件:

1、如果上一次最终没有满足条件,回溯出来后如果我们还在拼第一根(cur==0),那么必定失败

2、如果上一次失败回溯出来后,我们正好满足现在的长度加上当前木棍长度==目标长度(cur+a[i]==len),那么必定失败

3、我们要跳过和当前长度相同的木棍,因为用这个长度必定失败

代码:
#include<bits/stdc++.h>using namespace std;const int N=70;int n;int len,sum;
int a[N];
bool st[N];//记录状态 
//cur表示当前的长度
//u表示拼接的个数 
//start表示从第几根开始拼 
bool dfs(int u,int cur,int start)
{if(u*len==sum)return true;//拼成所有的 if(cur==len)return dfs(u+1,0,0);for(int i=start;i<n;i++){if(st[i])continue;if(cur+a[i]<=len){st[i]=true;//表示第i根已经用过了 if(dfs(u,cur+a[i],i+1))return true;st[i]=false;}if(!cur || cur+a[i]==len)return false;//如果当前在拼新木棍或者是最后一根品好的木棍 int j=i+1;while(j<n && a[j]==a[i])j++;//跳过长度相同的木棍 i=j-1;}return false;
}int main()
{while(cin>>n,n!=0){len=sum=0;memset(st,false,sizeof st);for(int i=0;i<n;i++){cin>>a[i];	sum+=a[i];len=max(len,a[i]);} sort(a,a+n,greater<int>());while(true){if(sum%len==0 && dfs(0,0,0)){cout<<len<<endl;break;}len++;}}return 0;	
} 

3、飞机降落(第十四届蓝桥杯省赛C++ B组)

有 N 架飞机准备降落到某个只有一条跑道的机场。

其中第 i 架飞机在 Ti时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早可以于 Ti 时刻开始降落,最晚可以于 Ti+Di 时刻开始降落。

降落过程需要 Li个单位时间。

一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。

请你判断 N 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。

第一行包含一个整数 T,代表测试数据的组数。

对于每组数据,第一行包含一个整数 N。

以下 N 行,每行包含三个整数:Ti,Di 和 Li。

输出格式

对于每组数据,输出 YES 或者 NO,代表是否可以全部安全降落。

数据范围

对于 30% 的数据,N≤2。
对于 100% 的数据,1≤T≤10,1≤N≤10,0≤Ti,Di,Li≤1e5。

输入样例:
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
输出样例:
YES
NO
样例解释

对于第一组数据,可以安排第 3 架飞机于 0 时刻开始降落,20 时刻完成降落。安排第 2 架飞机于 20时刻开始降落,30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落,40 时刻完成降落。

对于第二组数据,无论如何安排,都会有飞机不能及时降落。

思路:

关键:我们飞机最可以降落的最早时间是max(last,t)+l,因为就算飞机可以降落了,上一个飞机没有降落完成也是不行的,必须等到last结束才能降落,所以上上一辆飞机降落的时间取为max(last,t)+l

代码:
#include<bits/stdc++.h>using namespace std;const int N=20;struct plane
{int t,d,l;
}p[N]; int k,n;
int t[N],d[N],l[N];
bool st[N];//bool cmp(plane a,plane b)
//{
//	return a.t<b.t;
//}bool dfs(int cnt,int last)
{if(cnt>=n)//飞机达到数量 {return true;}for(int i=0;i<n;i++){int t=p[i].t;int d=p[i].d;int l=p[i].l;if(!st[i] && t+d>=last){st[i]=true;if(dfs(cnt+1,max(last,t)+l))return true;st[i]=false;}}return false;
}int main()
{cin>>k;while(k--){cin>>n;for(int i=0;i<n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);p[i]={a,b,c};}memset(st,false,sizeof st);if(dfs(0,0))cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;	
} 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/282525.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL数据库索引

目录 一.索引的基本内容 1.索引的定义 2.索引的作用 &#xff08;1&#xff09;设置了合适的索引之后&#xff0c;数据库利用各种快速定位技术&#xff0c;能够大大加快查询速度&#xff0c;这是创建索引的最主要的原因。 &#xff08;2&#xff09;当表很大或查询涉及到多…

鸿蒙一次开发,多端部署(四)工程管理

DevEco Studio的基本使用&#xff0c;请参考DevEco Studio使用指南。本章主要介绍如何使用DevEco Studio进行多设备应用开发。 说明&#xff1a; 本章的内容基于DevEco Studio 3.1.1 Release版本进行介绍&#xff0c;如您使用DevEco Studio其它版本&#xff0c;可能存在文档与产…

python --- 练习题3

目录 1、猜数字游戏&#xff08;使用random模块完成&#xff09; &#xff1a;继上期题目&#xff0c;附加 2、用户登录注册案例 3、求50~150之间的质数是那些&#xff1f; 4、打印输出标准水仙花数&#xff0c;输出这些水仙花数 5、验证:任意一个大于9的整数减去它的各位…

行业模板|DataEase制造行业大屏模板推荐

DataEase开源数据可视化分析平台于2022年6月发布模板市场&#xff08;https://templates-de.fit2cloud.com&#xff09;&#xff0c;并于2024年1月新增适用于DataEase v2版本的模板分类。模板市场旨在为DataEase用户提供专业、美观、拿来即用的大屏模板&#xff0c;方便用户根据…

机器学习_正则化

文章目录 代价函数 如果我们有非常多的特征&#xff0c;我们通过学习得到的假设可能能够非常好地适应训练集&#xff08;代价函数可能几乎为 0&#xff09;&#xff0c;但是可能会不能推广到新的数据。 下图是一个回归问题的例子&#xff1a; 第一个模型是一个线性模型&#xf…

思科网络中DHCP协议的配置

一、什么是DHCP&#xff1f;DHCP有什么作用&#xff1f; &#xff08;1&#xff09;DHCP&#xff08;Dynamic Host Configuration Protocol&#xff09;是一种网络协议&#xff0c;用于在局域网中自动分配IP地址和其他网络配置信息给计算机设备。我们电脑连接WiFi的时一般就是…

鸿蒙一次开发,多端部署(三)应用UX设计原则

设计原则 当为多种不同的设备开发应用时&#xff0c;有如下设计原则&#xff1a; 差异性 充分了解所要支持的设备&#xff0c;包括屏幕尺寸、交互方式、使用场景、用户人群等&#xff0c;对设备的特性进行针对性的设计。 一致性 除了要考虑每个设备的特性外&#xff0c;还…

VMD + CEEMDAN 二次分解,CNN-Transformer预测模型

往期精彩内容&#xff1a; 时序预测&#xff1a;LSTM、ARIMA、Holt-Winters、SARIMA模型的分析与比较-CSDN博客 风速预测&#xff08;一&#xff09;数据集介绍和预处理-CSDN博客 风速预测&#xff08;二&#xff09;基于Pytorch的EMD-LSTM模型-CSDN博客 风速预测&#xff…

【Excel自动化办公】使用openpyxl对Excel进行读写操作

目录 一、环境安装 1.1 创建python项目 1.2 安装openpyxl依赖 二、Excel数据读取操作 三、Excel数据写入操作 3.1 创建空白工作簿 3.2 写数据 四、设置单元格样式 4.1 字体样式 4.2 设置单元格背景填充色 4.3 设置单元格边框样式 4.4 单元格对齐方式 4.5 数据筛选…

Manga image Translator: 一键翻译各类图片内文字支持多种语言开源AI工具

项目地址&#xff1a;GitHub - zyddnys/manga-image-translator: Translate manga/image 一键翻译各类图片内文字 https://cotrans.touhou.ai/ 官方演示&#xff1a; https://touhou.ai/imgtrans/ 夸克网盘文件包下载链接&#xff1a;夸克网盘分享提取码&#xff1a;22G3 文…

基于高斯模型的运动目标检测(车辆检测),Matlab实现

博主简介&#xff1a; 专注、专一于Matlab图像处理学习、交流&#xff0c;matlab图像代码代做/项目合作可以联系&#xff08;QQ:3249726188&#xff09; 个人主页&#xff1a;Matlab_ImagePro-CSDN博客 原则&#xff1a;代码均由本人编写完成&#xff0c;非中介&#xff0c;提供…

数值分析(三) Lagrange(拉格朗日)插值法及Matlab代码实现

目录 前言一、Lagrange&#xff08;拉格朗日&#xff09;插值1. 线性插值2. 抛物插值3. 拉格朗日插值多项式 二、Lagrange插值算法及matlab代码1. Lagrange 插值算法matlab实现2 实例3. 线性插值示意图代码4. 抛物插值示意图代码 三、总结四、插值法专栏 前言 本篇为插值法专栏…

Linux学习之自定义协议

前言&#xff1a; 首先对于Tcp的socket的通信&#xff0c;我们已经大概了解了&#xff0c;但是其中其实是由一个小问题&#xff0c;我们目前是不得而知得&#xff0c;在我们客户端与服务端连接成功后&#xff0c;服务端读取来自客户端得消息&#xff0c;我们使用的是函数read,…

高通 8255 基本通信(QUP)Android侧控制方法说明

一&#xff1a;整体说明 高通8255芯片中&#xff0c;SPI IIC UART核心统一由QUP V3 进行控制 QUP V3为可编程模块&#xff0c;可以将不同通道配置为SPI IIC UART通路&#xff0c;此部分配置在QNX侧 QUP 资源可以直接被QNX使用&#xff0c;Android侧可以通过两种方法使用QUP资源…

YOLOv5-Y5周:yolo.py文件解读

本文为&#x1f517;365天深度学习训练营 中的学习记录博客 原作者&#xff1a;K同学啊|接辅导、项目定制 我的环境&#xff1a; 1.语言&#xff1a;python3.7 2.编译器&#xff1a;pycharm 3.深度学习框架Tensorflow/Pytorch 1.8.0cu111 一、代码解读 import argparse i…

idea将非UTF-8的properties修改为UTF-8编码的文件

需求背景 由于项目初始化时&#xff0c;properties文件的编码格式为ASCII编码格式&#xff0c;此时用idea打开该文件会默认展示UTF-8的编码内容&#xff0c;其中汉字可以正常展示&#xff0c;但是使用notepad打开却依旧时ASCII编码格式 idea配置 打开idea-setting-editor-f…

QT C++ QButtonGroup应用

//QT 中&#xff0c;按钮数量比较少&#xff0c;可以分别用各按钮的信号和槽处理。 //当按钮数量较多时&#xff0c;用QButtonGroup可以实现共用一个槽函数&#xff0c;批量处理&#xff0c;减少垃圾代码&#xff0c; //减少出错。 //开发平台&#xff1a;win10QT6.2.4 MSVC…

【LIMS】微服务

目录 一、服务解决方案-Spring Cloud Alibaba1.1选用原因&#xff08;基于Spring Cloud Alibaba的试用场景&#xff09;1.2 核心组件使用前期规划 部署 nacos部署 mino使用JavaFreemarker模板引擎&#xff0c;根据XML模板文件生成Word文档使用JavaFlowable 工作流引擎前端 -vue…

taro之Picker,PickerView基础用法

1.Picker 直接上代码 import Taro,{Component} from "tarojs/taro"; import {View,Picker} from tarojs/components import { AtIcon } from taro-ui import { putKey } from /src/utils/storage-utilsclass AgriculturePolicy extends Component{constructor (prop…

什么是浏览器指纹识别?Maskfog指纹浏览器有用吗?

浏览器指纹识别是好是坏&#xff1f;这现在确实是一个有争议的话题。83%的消费者经常或偶尔会根据浏览历史记录看到广告。其实这就是利用了浏览器指纹技术。 如果您想了解浏览器指纹识别是什么&#xff0c;那就看下去&#xff01; 一、什么是浏览器指纹识别 浏览器指纹是指无…