【真题解析】题目 3151: 蓝桥杯2023年第十四届省赛真题-飞机降落【C++ DFS 超详解注释版本】

本文主要是介绍【真题解析】题目 3151: 蓝桥杯2023年第十四届省赛真题-飞机降落【C++ DFS 超详解注释版本】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

爆搜冥想

  • 暴力枚举每一辆飞机
  • 对于每一个飞机都只存在两种情况,可以降落和不可以降落
  • 如果可以降落,计算降落后最早可以降落的时间pre,作为下一次递归的传参
  • 如果不可以降落,枚举下一辆飞机

注意这辆的降落有盘旋这种量子叠加态!
说人话就是:

  • 降落时有两种情况,一种是开始降落时间比pre后,那么从这个降落时间开始往后计算进行下一次递归即可。
  • 还有一种就是,在盘旋的状态中可以降落,那么就直接用pre计算下一次最早降落的时间,也就是结束盘旋状态立即降落。

核心出装

//plane.st:最早开始时间	plane.con:可持续时间 plane.netm:落地需要的时间 
bool dfs(vector<plane> &v,vector<bool> &bl,int pre,int count){			//pre和count默认是为0的 if(count==v.size()) return true;									//如果搜索了全部的飞机,函数返回true             for(int i=0;i<v.size();i++){										//遍历数组中所有飞机                if(bl[i] == false){												//如果找到一架飞机没有降落就使它降落 bl[i] = true;												//将该飞机的状态设置为已经降落 if(pre < v[i].st){											//如果这辆斐济满足降落条件 if(dfs(v, bl, v[i].st+v[i].netm, count+1)) return true;	//继续搜索这辆飞机降落后的时间,如果满足返回true }else if(pre <= v[i].st+v[i].con){							//如果这辆飞机盘旋后可以满足降落条件 if(dfs(v, bl, pre+v[i].netm, count+1)) return true;		//让这一架飞机立即降落,搜索它降落后的情况,满足返回true }bl[i] = false;												//如果不满足降落条件,将这辆飞机的状态恢复成false }}return false;														//搜索结束找不到返回false 
}

返回泉水

// 蓝桥真题-飞机降落 
#include<bits/stdc++.h>
using namespace std;
class plane{
public:int st;//最早开始时间 int con;//可持续费的时间 int netm;//落地需要的时间  plane(int s,int c,int ne){st=s;con=c;netm=ne;} 
};
//plane.st:最早开始时间	plane.con:可持续时间 plane.netm:落地需要的时间 
bool dfs(vector<plane> &v,vector<bool> &bl,int pre,int count){			//pre和count默认是为0的 if(count==v.size()) return true;									//如果搜索了全部的飞机,函数返回true             for(int i=0;i<v.size();i++){										//遍历数组中所有飞机                if(bl[i] == false){												//如果找到一架飞机没有降落就使它降落 bl[i] = true;												//将该飞机的状态设置为已经降落 if(pre < v[i].st){											//如果这辆斐济满足降落条件 if(dfs(v, bl, v[i].st+v[i].netm, count+1)) return true;	//继续搜索这辆飞机降落后的时间,如果满足返回true }else if(pre <= v[i].st+v[i].con){							//如果这辆飞机盘旋后可以满足降落条件 if(dfs(v, bl, pre+v[i].netm, count+1)) return true;		//让这一架飞机立即降落,搜索它降落后的情况,满足返回true }bl[i] = false;												//如果不满足降落条件,将这辆飞机的状态恢复成false }}return false;														//搜索结束找不到返回false 
}
int main(){int t;cin>>t;						//输入测试数据总数 while(t--){					//执行对应次数 int n;					//输入飞机数量 cin>>n;vector<plane> v;		//初始化动态数组存放飞机 vector<bool> bl(n,false);	//每一辆飞机的状态初始化为false while(n--){				//输入每一架飞机的信息 int t,d,l;			 cin>>t>>d>>l;v.push_back(plane(t,d,l));		//将该飞机推入动态数组 }if(dfs(v,bl,0,0)) cout<<"YES"<<endl;	//如果搜索到一种情况能使得飞机们降落返回true else cout<<"NO"<<endl;					//否则返回false }return 0;
}

结语🤣

这一次blog尝试了比较抽象的标题,这里进行解读:

  • 爆搜冥想:即核心思想,思路过程。
  • 核心出装:即完成功能的主要实现函数,dfs函数。
  • 返回泉水:即所有代码的一览。

编译环境

C++ 11 && DevC++
在这里插入图片描述

这篇关于【真题解析】题目 3151: 蓝桥杯2023年第十四届省赛真题-飞机降落【C++ DFS 超详解注释版本】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/852061

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d