蓝桥杯-dfs搜索模板题(一)

蓝桥杯-dfs搜索模板题(一)

  • P2089 烤鸡
  • P1088 火星人
  • P1149 火柴棒等式
  • P2036 PERKET
  • P1135 奇怪的电梯
  • 结语

P2089 烤鸡

在这里插入图片描述
对于每个位置枚举数字

#include<bits/stdc++.h>using namespace std;const int N=10+10;int n;int arr[N];//临时方案 int res=0;//方案数int mem[1000000][N];//所有方案 void dfs(int x,int sum)//x是位数,sum是已选的总质量 {if(sum>n)return;if(x>10){if(sum==n){res++;for(int i=1;i<=10;i++){mem[res][i]=arr[i];}}return;}for(int i=1;i<=3;i++){arr[x]=i;dfs(x+1,sum+i);arr[x]=0;} }int main(){scanf("%d",&n);dfs(1,0);printf("%d\n",res);for(int i=1;i<=res;i++){for(int j=1;j<=10;j++){printf("%d ",mem[i][j]);}printf("\n");}return 0;} 

P1088 火星人

在这里插入图片描述
在这里插入图片描述
本质也是对着位置枚举数字但是是在火星人给定的基础上,不然要搜索的太多了会爆

#include<bits/stdc++.h>
using namespace std;int n, m, res;
const int N = 10010;
int arr[N];
int mars[N];
bool st[N];
bool return0 = false;void dfs(int x)
{if (return0)return;//找到之后就不用往后搜了 //跟上面那个不一样,这个位数最多有10000太多了不能全部遍历 if (x > n){res++;if (res == m + 1){return0 = true;for (int i = 1; i <= n; i++){cout << arr[i] << ' ';}}return;}for (int i = 1; i <= n; i++){if (!res){i = mars[x];//从火星人给的开始枚举 }if (!st[i]){st[i] = true;arr[x] = i;dfs(x + 1);st[i] = false;arr[x] = 0;}}
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> mars[i];dfs(1);return 0;
}

P1149 火柴棒等式

在这里插入图片描述
按照题目要求去搜索暴力。
经验之谈,最多应是711,多试几个可以试出来

#include<bits/stdc++.h>
using namespace std;
const int N= 10010;
int n;
int arr[N];
int res=0;
int nums[N]={6,2,5,5,4,5,6,3,7,6};//存火柴棍 int col(int x)//计算火柴棍数量 
{if(nums[x]) return nums[x];else{int sumfire=0;while(x){sumfire+=nums[x%10];x/=10;}return sumfire;} 
}void dfs(int x,int sum)
{if(sum>n) return ;if(x>3){if(arr[1]+arr[2]==arr[3]&&sum==n){res++;}return;}for(int i=0;i<=1000;i++) {arr[x]=i;dfs(x+1,sum+nums[i]);arr[x]=0;}
}int main()
{cin>>n;n-=4;for(int i=10;i<=1000;i++){nums[i]=nums[i%10]+nums[i/10];}dfs(1,0); 	cout<<res;return 0;}

P2036 PERKET

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;const int N=20;int n;int acid[N],bitter[N];
int res=1e9;//存答案 
int st[N];//0未考虑 1选2不选void dfs(int x)
{if(x>n){bool has=false;int sum1=1;//酸度之积 int sum2=0;//苦度之和for(int i=1;i<=n;i++){if(st[i]==1){has=true;sum1*=acid[i];sum2+=bitter[i];	}}if(has) res=min(res,abs(sum1-sum2));//有得选才走,啥都不选返回1没价值return ; }//选st[x]=1;dfs(x+1);st[x]=0;//不选st[x]=2;dfs(x+1);st[x]=0;
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>acid[i]>>bitter[i];dfs(1);cout<<res;return 0;
}

P1135 奇怪的电梯

在这里插入图片描述
每层只走一次的方案一定比每次重复走的方案好,用st来记录有没有走过。
这道题用以下代码只能过一部分,也是暴力的局限之处。得有更好的优化或其他方法

#include<bits/stdc++.h>
using namespace std;
const int N=10010;int n,A,B;
int evlt[N];
int res=1e9;
bool st[N];
//当前在x楼,按了cnt次按钮 
void dfs(int x,int cnt)
{if(cnt>=res)return;if(x>n||x<0)return ;if(x==B){res=min(res,cnt);return ;} //上if(x+evlt[x]<=n&&!st[x+evlt[x]]){st[x+evlt[x]]=true;dfs(x+evlt[x],cnt+1); st[x+evlt[x]]=false;}	//下if(x-evlt[x]>0&&!st[x-evlt[x]]){st[x-evlt[x]]=true;dfs(x-evlt[x],cnt+1); st[x-evlt[x]]=false;}}int main()
{cin>>n>>A>>B;for(int i=1;i<=n;i++){cin>>evlt[i];}dfs(A,0);if(res==1e9){cout<<-1;return 0;}cout<<res;return 0;}

结语

整理自链接: link

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

AI音乐GPT时刻来临:Suno 快速入门手册!

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

搜索二维矩阵 II - LeetCode 热题 21

大家好&#xff01;我是曾续缘&#x1f497; 今天是《LeetCode 热题 100》系列 发车第 21 天 矩阵第 4 题 ❤️点赞 &#x1f44d; 收藏 ⭐再看&#xff0c;养成习惯 搜索二维矩阵 II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&…

软件架构风格_2.调用/返回体系结构风格

调用/返回风格是指在系统中采用了调用与返回机制。利用调用-返回实际上是一种分而治之的策略&#xff0c;其主要思想是将一个复杂的大系统分解为若干子系统&#xff0c;以便降低复杂度&#xff0c;并且增加可修改性。程序从其执行起点开始执行该构件的代码&#xff0c;程序执行…

Groovy 介绍、下载、语法

Groovy 简介 Groovy 可以被视为Java 的一种脚本化改良版&#xff0c;Groovy 也是运行在 JVM 上&#xff0c;可以很好地与 Java 代码及其相关库进行交互操作。Groovy 是一种成熟的面向对象编程语言&#xff0c;既可以面向对象编程&#xff0c;又可以用作纯粹的脚本语言。大多数…

融资融券有什么优点和缺点?融资利率和费率多少?

融资融券是一种证券信用交易&#xff0c;指投资者向具有融资融券业务资格的证券公司提供担保物&#xff0c;借入资金买入证券或者借入证券并卖出的行为 融资融券的优点有&#xff1a; 增加交易资金。投资者可以通过融资融券账户&#xff0c;向证券公司借入资金&#xff0c;增加…

sa-token非Web上下文无法获取Request

0x02 非Web上下文无法获取Request 问题定位 在我们使用sa-token安全框架的时候&#xff0c;有时候会提示&#xff1a;**SaTokenException:非Web上下文无法获取Request**** 错误截图&#xff1a; 在官方网站中&#xff0c;查看常见问题排查&#xff1a; 非Web上下文无法获取…

QT使用数据库和proC数据库

一&#xff0c;QT使用数据库 数据库就是保存数据的文件。可以存储大量数据&#xff0c;包括插入数据、更新数据、截取数据等。用专业术语来说&#xff0c;数据库是“按照数据结构来组织、存储和管理数据的仓库”。 什么时候需要数据库&#xff1f;在嵌入式里&#xff0…

每日一题(leetcode169):多数元素-哈希、随机、分治

哈希&#xff1a; class Solution { public:int majorityElement(vector<int>& nums) {int lennums.size();unordered_map<int,int> map;for (int i0;i<len;i){if(map.find(nums[i])map.end()){map[nums[i]]1;}else{map[nums[i]];}}int seqlen/2;int ansnu…

FebHost:注册人工智能.AI域名的优势?

近年来,人工智能技术的飞速发展,让AI在各行各业扮演着愈发重要的角色。在这一背景下,.AI域名凭借其独特的优势,正成为越来越多AI从业者的首选。那么,.AI域名到底有哪些亮点,值得广大AI企业和个人关注呢?记者进行了深入探访。 专业形象加分 彰显技术实力 要说.AI域名的最大优势…

yolov5关键点检测-实现溺水检测与警报提示(代码+原理)

基于YOLOv5的关键点检测应用于溺水检测与警报提示是一种结合深度学习与计算机视觉技术的安全监控解决方案。该项目通常会利用YOLOv5强大的实时目标检测能力&#xff0c;并通过扩展或修改网络结构以支持人体关键点检测&#xff0c;来识别游泳池或其他水域中人们的行为姿态。 项…

为何网易游戏会选择引入OceanBase数据库

本文作者&#xff1a;田维繁&#xff0c;网易游戏关系型数据库小组负责人 作为中国游戏开发领域的佼佼者&#xff0c;网易游戏始终站在网络游戏自主研发的前沿。其产品及周边产品线丰富多样&#xff0c;因此&#xff0c;为满足各种业务场景的需求&#xff0c;需要多种不同的数据…

delphi获取windows右下角任务栏图标信息

今天在群里,看有人问怎么获取windows右下角任务栏图标信息 win7 x64 测试通过 unit Unit1;interfaceusesWinapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,Vcl.Controls, Vcl.Forms, Vcl.Dialogs,commctrl, Vcl.StdCtr…

烂笔头笔记:Windows 11下照片查看器显示偏色问题修复

本文出处&#xff1a;http://blog.csdn.net/chaijunkun/article/details/137278931&#xff0c;转载请注明。由于本人不定期会整理相关博文&#xff0c;会对相应内容作出完善。因此强烈建议在原始出处查看此文。 最近在研究HDR视频的截图算法&#xff0c;目的就是生成色彩正确…

并发编程01-深入理解Java并发/线程等待/通知机制

为什么我们要学习并发编程&#xff1f; 最直白的原因&#xff0c;因为面试需要&#xff0c;我们来看看美团和阿里对 Java 岗位的 JD&#xff1a; 从上面两大互联网公司的招聘需求可以看到&#xff0c; 大厂的 Java 岗的并发编程能力属于标配。 而在非大厂的公司&#xff0c; 并…

如何在 Android 上恢复已删除的短信

在 Android 上恢复短信是一件棘手的事情。以下是限制、您的选择以及如何为未来做好准备。 丢失手机数据令人心碎。无论您不小心删除了某些内容&#xff0c;还是手机被盗或损坏&#xff0c;您不可替代的照片、亲人的消息等都可能会立即消失。 如果您需要从 Android 手机恢复一…

腾讯云最新活动及优惠券领取入口整理汇总

腾讯云作为国内领先的云服务提供商&#xff0c;始终致力于为广大用户提供更优质、更便捷的云服务体验。为了帮助用户更好地了解和参与腾讯云的活动&#xff0c;本文将对腾讯云的最新活动及优惠券领取入口进行整理汇总。 一、优惠券领取入口 领取入口&#xff1a;点此领取 领券…

OSPF实验1

1,配置IP地址 [R1]dis ip interface brief Interface IP Address/Mask Physical Protocol GigabitEthernet0/0/0 200.1.1.1/24 up up GigabitEthernet0/0/1 10.1.1.1/24 up …

Linux学习笔记————C 语言版 LED 灯实验

这里写目录标题 一、实验程序编写二、 汇编部分实验程序编写三、C 语言部分实验程序编写四、编译下载验证 汇编 LED 灯实验中&#xff0c;我们讲解了如何使用汇编来编写 LED 灯驱动&#xff0c;实际工作中是很少用到汇编去写嵌入式驱动的&#xff0c;毕竟汇编太难&#xff0c;而…

加密、签名、验签、证书、对称加密、非对称加密【部分知识点】

文章目录 前言如图一些概念区分不可逆加密可逆加密签名和验签 前言 总结一些涉及到OTA升级相关的数据加密知识点&#xff0c;仅作为笔记记录&#xff0c;仅部分总结&#xff0c;细节部分可以私聊我。 如图 一些概念区分 不可逆加密 哈希算法是一个统称&#xff0c;它分为MD…

HarmonyOS 应用开发之同应用跨设备数据同步

概述 场景介绍 跨设备数据同步功能&#xff08;即分布式功能&#xff09;&#xff0c;指将数据同步到一个组网环境中的其他设备。常用于用户应用程序数据内容在可信认证的不同设备间&#xff0c;进行自由同步、修改和查询。 例如&#xff1a;当设备1上的应用A在分布式数据库…