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

李白打酒加强版 -- 题解 c++

题目链接 : 

4408. 李白打酒加强版 - AcWing题库

用户登录

二进制搜索

只能过10%,极限暴力

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;int n , m , p ;string f(int x){string s = bitset<32>(x).to_string() ;return s.substr(16) ;
}int get(LL x){int cnt = 0 ;while(x){x = x & (x-1) ;cnt ++ ;}return cnt  ;
}bool pd(int x){if(get(x)!=n) return false ;int f = 2 ;for(int i=p-1;i>=0;i--){if((x>>i)&1) f *= 2 ;else{if(f==0) return false ;f--;}}if(f==0) return true ;else return false ;
}inline void solve(){cin >> n >> m ;p = n + m ;// 0 : 花 , 1 : 酒 LL ans = 0 ;for(int i=0;i<(1<<p);i++){if(pd(i)){ans ++ ;
//			cout << f(i) << endl ;}}cout << ans << endl ;	 
}signed main()
{IOSint _ = 1;while(_ --) solve();return 0;
}

DFS

没啥好讲的,直接看代码,能过、40%

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7 ;
typedef long long LL;
int n , m ;
LL ans ;void dfs(int i,int j,int k,int z){//i次店,j次花,剩余k酒,z:当前位置//最后一次必为花,且酒刚好为0if(z==n+m-1){//倒数第二次if(k==1&&i==n&&j==m-1){ans ++ ;}return ;}if(k<=0) return ;// 遇到店dfs(i+1,j,k*2,z+1);//遇到花dfs(i,j+1,k-1,z+1);
}int main(){cin >> n >> m ; // 店n次,花m次dfs(0,0,2,0);ans = ans % MOD ;cout << ans << endl ;return 0 ;
}

DP

dp[i][j][k] 表示为前i次,有j次遇到店,剩下酒为k斗 的方案数

详细请看题解

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7 ;
const int N = 201 ;
typedef long long LL;
int n , m ;
LL ans ;
LL dp[N][N][N] ;// dp[i][j][k] 表示为前i次,有j次遇到店,剩下酒为k斗 的方案数int main(){cin >> n >> m ; // 店n次,花m次dp[0][0][2] = 1 ;//初始2for(int i=1;i<=n+m;i++){for(int j=0;j<=n;j++){for(int k=0;k<=100;k++){//最多消耗100瓶// 上一次遇到花dp[i][j][k] += dp[i-1][j][k+1];// 上一次遇到酒if(j && k%2==0){dp[i][j][k] += dp[i-1][j-1][k/2] ;}dp[i][j][k] %= MOD ;}}}dp[n+m][n][0] = dp[n+m-1][n][1] ;cout << dp[n+m][n][0] << endl ;return 0 ;
}

 

相关文章:

李白打酒加强版 -- 题解 c++

题目链接 : 4408. 李白打酒加强版 - AcWing题库 用户登录 二进制搜索 只能过10%,极限暴力 #include<bits/stdc.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl \n typedef long long LL; const int mod 1e97; const int N 2e510;…...

蓝桥杯——玩具蛇

题目 小蓝有—条玩具蛇&#xff0c;一共有16节&#xff0c;上面标着数字1至16。每—节都是一个正方形的形状。相邻的两节可以成直线或者成90度角。 小蓝还有一个44的方格盒子&#xff0c;用于存放玩具蛇&#xff0c;盒子的方格上依次标着字母A到Р共16个字母。 小蓝可以折叠自…...

百度SSL证书免费申请

百度云也有免费SSL证书可以申请&#xff0c;很多用户找不到&#xff0c;云服务器吧yunfuwuqiba.com整理百度云SSL免费证书申请入口&#xff1a; 1、打开百度云SSL证书购买页面 yunfuwuqiba.com/go/baidu_ssl 点立即购买&#xff0c;如下图&#xff1a; 百度云SSL证书 2、免费…...

SpringBoot Assert断言

文章目录 前言一、Assert说明二、Assert方法三、使用示例四、总结前言 在Spring Boot中,Assert类提供了一系列用于断言的静态方法,用于在代码中进行条件检查和错误处理。这些方法可以帮助我们在开发过程中快速发现和解决问题,提高代码的可靠性和健壮性。 一、Assert说明 在…...

test4121

欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;滤波估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能等相关领域的知识和…...

UI自动化测试重点思考(下)--装饰器/生成器/夹具的使用/描述符的作用/ddt驱动/多线程

UI自动化测试重点思考--装饰器 装饰器装饰器定义装饰器代码示例装饰器的执行如何将装饰器融合到pytest框架里面 生成器创建生成器生成器的定义如何将生成器融合到pytest框架里面 fixture&#xff08;夹具&#xff09;使用pytest fixture 中 scope 参数的详细解释 描述符的总结描…...

C# 字段和属性的区别

区别 在C#中&#xff0c;字段&#xff08;Field&#xff09;和属性&#xff08;Property&#xff09;都是用来封装对象状态的方式&#xff0c;但它们有以下区别&#xff1a; 访问级别&#xff1a; 字段通常是private&#xff0c;而属性可以有不同级别的访问限制&#xff08;…...

备考ICA----Istio实验17---TCP流量授权

备考ICA----Istio实验17—TCP流量授权 1. 环境准备 1.1 环境部署 kubectl apply -f <(istioctl kube-inject -f istio/samples/tcp-echo/tcp-echo.yaml) -n kim kubectl apply -f <(istioctl kube-inject -f istio/samples/sleep/sleep.yaml) -n kim1.2 测试环境 检测…...

[C++][算法基础]树的重心(树图DFS)

给定一颗树&#xff0c;树中包含 n 个结点&#xff08;编号 1∼n&#xff09;和 n−1 条无向边。 请你找到树的重心&#xff0c;并输出将重心删除后&#xff0c;剩余各个连通块中点数的最大值。 重心定义&#xff1a;重心是指树中的一个结点&#xff0c;如果将这个点删除后&a…...

探秘ChatGPT:如何利用AI提升论文写作效率

ChatGPT无限次数:点击直达 html 探秘ChatGPT&#xff1a;如何利用AI提升论文写作效率 在当今信息爆炸的时代&#xff0c;论文写作是许多人工作者每天都要面对的任务。如何更高效地撰写出内容丰富、结构严谨的论文&#xff0c;一直是许多学者和研究人员所追求的目标。随着人…...

多无人机集群协同避障

matlab2020a正常运行 场景1规划结果 场景2规划结果 场景3规划结果 代码地址&#xff1a; 多无人机集群协同避障效果&#xff08;5架&#xff09;资源-CSDN文库...

基于velero和minio实现k8s数据的备份

1.30部署minio rootk8s-harbor:/etc/kubeasz/clusters/k8s-cluster1# docker run \ -d --restartalways -p 9000:9000 -p 9090:9090 –name minio -v /data/minio/data:/data -e “MINIO_ROOT_USERadmin” -e “MINIO_ROOT_PASSWORD12345678” quay.io/minio/minio server…...

【Java核心技术】第4章 对象与类

1 面向对象 2 自定义类 形式&#xff1a; class ClassName { field // 字段 constructor // 构造器&#xff08;构造函数&#xff09; method // 方法 } 如&#xff1a; class Employee {private String name;private double salary;private LocalDate hireDay;public Emp…...

【LeetCode】回溯算法类题目详解

所有题目均来自于LeetCode&#xff0c;刷题代码使用的Python3版本 回溯算法 回溯算法是一种搜索的方法&#xff0c;在二叉树总结当中&#xff0c;经常使用到递归去解决相关的问题&#xff0c;在二叉树的所有路径问题中&#xff0c;我们就使用到了回溯算法来找到所有的路径。 …...

java实现请求缓冲合并

业务背景&#xff1a; 我们对外提供了一个rest接口给第三方业务进行调用&#xff0c;但是由于第三方框架限制&#xff0c;导致会发送大量相似无效请求&#xff0c;例如&#xff1a;接口入参json包含两个字段&#xff0c;createBy和receiverList&#xff0c;完整的入参json示例…...

分布式锁的原子性问题

4.6 分布式锁的原子性问题 更为极端的误删逻辑说明&#xff1a; 线程1现在持有锁之后&#xff0c;在执行业务逻辑过程中&#xff0c;他正准备删除锁&#xff0c;而且已经走到了条件判断的过程中&#xff0c;比如他已经拿到了当前这把锁确实是属于他自己的&#xff0c;正准备删…...

从零自制docker-8-【构建实现run命令的容器】

文章目录 log "github.com/sirupsen/logrus"args...go moduleimport第三方包失败package和 go import的导入go build . 和go runcli库log.SetFormatter(&log.JSONFormatter{})error和nil的关系cmd.Wait()和cmd.Start()arg……context.Args().Get(0)syscall.Exec和…...

2024.03.31 校招 实习 内推 面经

绿*泡*泡VX&#xff1a; neituijunsir 交流*裙 &#xff0c;内推/实习/校招汇总表格 1、自动驾驶一周资讯 -小米SU7上市24小时&#xff0c;大定达88898台&#xff1b;小鹏汽车正式进入德国市场&#xff1b;地平线递交港股上市申请 自动驾驶一周资讯 -小米SU7上市24小时&…...

邦芒职场:塑造职场人气王的秘诀

在职场中&#xff0c;有些人总能吸引众人的目光&#xff0c;成为团队的焦点&#xff1b;而有些人却常常默默无闻&#xff0c;难以融入。那么&#xff0c;如何在职场中脱颖而出&#xff0c;成为一个受欢迎的人呢&#xff1f;下面&#xff0c;让我们来探讨一下塑造职场人气王的秘…...

滤波器网络变压器的作用

网络变压器的作用主要包括以下几点&#xff1a; 1. 信号传输&#xff1a;网络变压器可以将PHY送出来的差分信号用差模耦合的线圈耦合滤波以增强信号&#xff0c;并且通过电磁场的转换耦合到不同电平的连接网线的另外一端以达到传输数据的目的。 2. 电气电压隔离&#xff1a…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...