蓝桥杯-李白打酒加强版
蓝桥杯-李白打酒加强版
- 1、问题描述
- 2、解题思路
- 3、代码实现
1、问题描述
话说大诗人李白, 一生好饮。幸好他从不开车。
一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:
无事街上走,提显去打酒。 逢店加一倍, 遇花喝一斗。
这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?
注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。
输入格式
第一行包含两个整数 N 和 M.
输出格式
输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果.
样例输入
5 10
样例输出
14
样例说明
如果我们用 0 代表遇到花,1 代表遇到店,14 种顺序如下:
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
评测用例规模与约定
对于 40% 的评测用例: 1≤N,M≤10 。
对于 100% 的评测用例: 1≤N,M≤100 。
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
2、解题思路
直接暴力递归,用count计数,设计一个函数fun(int a,int b,int c),用a表示李白遇见的是店,b表示遇见的是花,c表示酒显中的剩余酒量。
-
递归出口:
(a==0&&b==1&&c==1),店没了,题中要求最后一次遇见的是花,所以b=1,因为遇见花要喝一斗酒,所以c=1 -
若遇见的是店:
fun(a-1,b,c*2);,店-1,酒量加倍。 -
若遇见的是花:
fun(a,b-1,c-1),花-1,酒量-1。
3、代码实现
private static int count=0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();System.out.println(fun(n,m,2));}public static int fun(int a,int b,int c){//出口:最后一次遇到花,说明店没有了,酒剩最后一抖,最后一次赏花后会喝完if(a==0&&b==1&&c==1){count++;}if(a>0){//碰到店了 酒量加倍fun(a-1,b,c*2);}//碰到花了,花-1,酒量-1if(b>1){fun(a,b-1,c-1);}return count;}

虽然做出来了,但这个只能通过40%的用例,剩下的60%超时了。最优解估计是DP,这个后面再研究吧。
相关文章:
蓝桥杯-李白打酒加强版
蓝桥杯-李白打酒加强版1、问题描述2、解题思路3、代码实现1、问题描述 话说大诗人李白, 一生好饮。幸好他从不开车。 一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱: 无事街上走,提显去打酒。 逢店加一倍, 遇花喝一斗。 这一路上, 他一共遇到店 N 次…...
AtCoder Beginner Contest 292 (A - E) 记录第一场ABC
AtCoder Beginner Contest 292 A - E前言Q1 A - CAPS LOCKQ2 Yellow and Red CardQ3 Four VariablesQ4 D - Unicyclic ComponentsQ5 E - Transitivity前言 本来晚上在打Acwing周赛,最后一题Trie想不出来咋写,看群里有人说ABC要开始了,想着没…...
ubuntu安装使用putty
一、安装 安装虚拟机串口 sudo apt-get install putty sudo apt install -y setserial 二、使用 虚拟机连接串口 sudo setserial -g /dev/ttyS* 查看硬件对应串口 找到不是unknown的串口 sudo putty...
【CS144】Lab5与Lab6总结
Lab5与Lab6Lab汇总Lab5概述Lab6概述由于Lab5和Lab6相对比较简单(跟着文档一步一步写就行),于是放在一起做一个简单概述(主要是懒得写了…) Lab汇总 Lab5概述 lab5要求实现一个IP与Ethernet(以太网&#x…...
GDScript 导出变量 (Godot4.0)
概述 导出变量的功能在3.x版本中也是有的,但是4.0版本对其进行了语法上的改进。 导出变量在日常的游戏制作中提供节点的自定义参数化调节功能时非常有用,除此之外还用于自定义资源。 本文是(Bilibili巽星石)在4.0官方文档《GDScr…...
shell:#!/usr/bin/env python作用是什么
我们经常会在别人的脚本文件里看到第一行是下面这样 #!/usr/bin/python或者 #!/usr/bin/env python 那么他们有什么用呢? 要理解它,得把这一行语句拆成两部分。 第一部分是 #! 第二部分是 /usr/bin/python 或者 /usr/bin/env python 关于 #! 这个…...
计算机行业AIGC算力时代系列报告-ChatGPT芯片算力:研究框架
报告下载: 计算机行业AIGC算力时代系列报告-ChatGPT芯片算力:研究框架 简介 “AI算力时代已经来临,计算机行业正在经历着一场前所未有的变革!” 这是一个充满活力和兴奋的时代,人工智能(AI)已…...
『MyBatis技术内幕』源码调试前提
准备源代码包 下载源代码 3.4.6 版本 https://github.com/mybatis/mybatis-3/releases?page2 通过 idea 导入然后回自动下载所有依赖,根据 3.4.6 版本的 pom.xml 找到依赖的 mybatis-parent 版本 <parent><groupId>org.mybatis</groupId><ar…...
# Linux最新2022年面试题大汇总,附答案
# Linux最新2022年面试题大汇总,附答案 ### [1、cp(copy单词缩写,复制功能)](最新2021年面试题大汇总,附答案.md#1cpcopy单词缩写复制功能) cp /opt/java/java.log /opt/logs/ ;把java.log 复制到/opt/logs/下 cp /…...
css中重难点整理
一、vertical-align 在学习vertical-align的时候,可能会很困惑。即使网上有一大推文章讲veitical-align,感觉看完好像懂了,等自己布局的时候用到vertical-align的时候好像对它又很陌生。这就是我在布局的时候遇到的问题。 本来vertical-align就很不好理…...
JavaScript-扫盲
文章目录1. 前言2. 第一个 JavaScript 程序3. javaScript 的基础语法3.1 变量3.2 数据类型3.3 运算符3.4 条件语句3.5 数组3.6 函数3.7 作用域3.8 对象4. WebAPI4.1 DOM 基本概念4.2 常用 DOM API4.3 事件4.4 操作元素4.5 网页版猜数字游戏4.6 留言版1. 前言 提问 java 和 java…...
bpftrace 笔记
bpftrace -e BEFIN {printf("hello world!\n");}获取调用 vfs_read 函数的进程id, 每2s打印一次 bpftrace -e kprobe:vfs_read {ID pid;} interval:s:2 {printf{"ID:%d\n", ID);}用户态调试 bpftrace -e uprobe:/*/a.out:and {printf("ID:%d\n&qu…...
DELL-Vostro-5468电脑 Hackintosh 黑苹果efi引导文件
原文来源于黑果魏叔官网,转载需注明出处。硬件型号驱动情况主板DELL-Vostro-5468处理器Intel Core i3-7100U 2.40 GHz, 3M Cache已驱动内存Samsung 8GB DDR4-2133MHz已驱动硬盘TOPMORE CAPRICORNUS NVMe 1TB已驱动显卡Intel HD Graphics 620已驱动声卡Realtek ALC2…...
阶段二11_面向对象高级_学生管理系统案例2
主要内容: 添加学生 static关键字一.添加学生时判断id是否存在 0.思路图片: 04/图片/2_添加学生判断id存在的问题分析.png 1.思路实现详细步骤: StudentController【客服接待】 /** 接收到学生id后,判断该id在数组中是否存在 这…...
spring源码篇(3)——bean的加载和创建
spring-framework 版本:v5.3.19 文章目录bean的加载bean的创建总结getBean流程createBean流程doCreateBean流程bean的加载 beanFactory的genBean最常用的一个实现就是AbstractBeanFactory.getBean()。 以ApplicationContext为例,流程是: ApplicationCon…...
Spring 中事务的传播级别
Spring 中事务的传播级别 REQUIRED(默认):默认的隔离级别,如果当前存在一个事务,就加入该事务,如果当前没有事务,就创建一个新的事务。 REQUIRED_NEW:不管当前是否存在事务,都创建一个新的事物…...
ECharts可视化库--常用组件
目录 一.series系列 二.常见组件 1.标题title 2.图例legend 3.工具栏toolbox 4.提示框tooltip 5.坐标轴 xAxis yAsix 6.series系列 上一篇已经介绍了ECharts库的导入工作和绘制基本的图标,今天我们来了解一下常用的组件,如果对数据可视化感兴…...
openpnp - 设备开机后, 吸嘴校验失败的解决方法
文章目录openpnp - 设备开机后, 吸嘴校验失败的解决方法概述重新校验吸嘴ENDopenpnp - 设备开机后, 吸嘴校验失败的解决方法 概述 设备开机后, 默认会校验吸嘴座上已经安装的2个吸嘴. 如果开机校验吸嘴失败, 就需要用向导重新校验失败的吸嘴. 具体是哪个吸嘴校验失败, 可以看…...
【Linux学习】基础IO——软硬链接 | 制作动静态库
🐱作者:一只大喵咪1201 🐱专栏:《Linux学习》 🔥格言:你只管努力,剩下的交给时间! 基础IO🍓软硬链接🌲软链接🌲硬链接🍓动静态库&…...
如何分辨on-policy和off-policy
on-policy的定义:behavior policy和target-policy相同的是on-policy,不同的是off-policy。 behavior policy:采样数据的策略,影响的是采样出来s,a的分布。 target policy:就是被不断迭代修改的策略。 如果是基于深度…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
